{"action":"created","issue":{"url":"https://api.github.com/repos/earwig/mwparserfromhell/issues/128","labels_url":"https://api.github.com/repos/earwig/mwparserfromhell/issues/128/labels{/name}","comments_url":"https://api.github.com/repos/earwig/mwparserfromhell/issues/128/comments","events_url":"https://api.github.com/repos/earwig/mwparserfromhell/issues/128/events","html_url":"https://github.com/earwig/mwparserfromhell/issues/128","id":113909619,"number":128,"title":"Implement Wikicode.nodes as a doubly-linked list","user":{"login":"Rua","id":3090610,"avatar_url":"https://avatars.githubusercontent.com/u/3090610?v=3","gravatar_id":"","url":"https://api.github.com/users/Rua","html_url":"https://github.com/Rua","followers_url":"https://api.github.com/users/Rua/followers","following_url":"https://api.github.com/users/Rua/following{/other_user}","gists_url":"https://api.github.com/users/Rua/gists{/gist_id}","starred_url":"https://api.github.com/users/Rua/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Rua/subscriptions","organizations_url":"https://api.github.com/users/Rua/orgs","repos_url":"https://api.github.com/users/Rua/repos","events_url":"https://api.github.com/users/Rua/events{/privacy}","received_events_url":"https://api.github.com/users/Rua/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/earwig/mwparserfromhell/labels/aspect:%20tree","name":"aspect: tree","color":"33AAEE"},{"url":"https://api.github.com/repos/earwig/mwparserfromhell/labels/priority:%20mid","name":"priority: mid","color":"EEAA33"}],"state":"open","locked":false,"assignee":{"login":"earwig","id":637235,"avatar_url":"https://avatars.githubusercontent.com/u/637235?v=3","gravatar_id":"","url":"https://api.github.com/users/earwig","html_url":"https://github.com/earwig","followers_url":"https://api.github.com/users/earwig/followers","following_url":"https://api.github.com/users/earwig/following{/other_user}","gists_url":"https://api.github.com/users/earwig/gists{/gist_id}","starred_url":"https://api.github.com/users/earwig/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/earwig/subscriptions","organizations_url":"https://api.github.com/users/earwig/orgs","repos_url":"https://api.github.com/users/earwig/repos","events_url":"https://api.github.com/users/earwig/events{/privacy}","received_events_url":"https://api.github.com/users/earwig/received_events","type":"User","site_admin":false},"milestone":{"url":"https://api.github.com/repos/earwig/mwparserfromhell/milestones/8","html_url":"https://github.com/earwig/mwparserfromhell/milestones/version%200.5","labels_url":"https://api.github.com/repos/earwig/mwparserfromhell/milestones/8/labels","id":1127195,"number":8,"title":"version 0.5","description":"Final easy-ish additions before the version 1.0 overhaul, including remaining node types (redirects) and other optimizations/fixes.","creator":{"login":"earwig","id":637235,"avatar_url":"https://avatars.githubusercontent.com/u/637235?v=3","gravatar_id":"","url":"https://api.github.com/users/earwig","html_url":"https://github.com/earwig","followers_url":"https://api.github.com/users/earwig/followers","following_url":"https://api.github.com/users/earwig/following{/other_user}","gists_url":"https://api.github.com/users/earwig/gists{/gist_id}","starred_url":"https://api.github.com/users/earwig/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/earwig/subscriptions","organizations_url":"https://api.github.com/users/earwig/orgs","repos_url":"https://api.github.com/users/earwig/repos","events_url":"https://api.github.com/users/earwig/events{/privacy}","received_events_url":"https://api.github.com/users/earwig/received_events","type":"User","site_admin":false},"open_issues":9,"closed_issues":0,"state":"open","created_at":"2015-05-23T23:35:39Z","updated_at":"2015-10-28T20:10:33Z","due_on":null,"closed_at":null},"comments":2,"created_at":"2015-10-28T19:59:15Z","updated_at":"2015-10-28T23:15:28Z","closed_at":null,"body":"In my experience, it's not very common to want random access to nodes by their index. Instead, it's more common to go through the list sequentially with one of the filter iterators, possibly skipping some along the way. Modifying the node list by insertion or deletion is doubly-slow with the current implementation: first the list has to be traversed to find the index of the insertion point, then to insert means that all subsequent elements have to be shifted over. Both insertion and deletion of nodes are common operations.\r\n\r\nSo I think that it would make more sense to use linked lists for this implementation. Insertion and deleting will be fast, and iteration is not affected, nor is searching. Indexing will be slow, but that's not such a common thing to do anyway. Another thing that is sorely needed is, given a node, to find the previous and following nodes. This is also much simpler and faster with a linked list, as it doesn't mean having to find the index first. I think that linked lists would also allow modifying the list during iteration, but I'm not sure. If possible, that would be yet another pro.\r\n\r\nIf this is done, it should probably be done for template parameters and other lists of nodes too."},"comment":{"url":"https://api.github.com/repos/earwig/mwparserfromhell/issues/comments/152025620","html_url":"https://github.com/earwig/mwparserfromhell/issues/128#issuecomment-152025620","issue_url":"https://api.github.com/repos/earwig/mwparserfromhell/issues/128","id":152025620,"user":{"login":"earwig","id":637235,"avatar_url":"https://avatars.githubusercontent.com/u/637235?v=3","gravatar_id":"","url":"https://api.github.com/users/earwig","html_url":"https://github.com/earwig","followers_url":"https://api.github.com/users/earwig/followers","following_url":"https://api.github.com/users/earwig/following{/other_user}","gists_url":"https://api.github.com/users/earwig/gists{/gist_id}","starred_url":"https://api.github.com/users/earwig/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/earwig/subscriptions","organizations_url":"https://api.github.com/users/earwig/orgs","repos_url":"https://api.github.com/users/earwig/repos","events_url":"https://api.github.com/users/earwig/events{/privacy}","received_events_url":"https://api.github.com/users/earwig/received_events","type":"User","site_admin":false},"created_at":"2015-10-28T23:15:28Z","updated_at":"2015-10-28T23:15:28Z","body":"Actually, @jfolz, I think you might be right. I recall that the overhead of linked lists (both in terms of memory usage and their conflicts with CPU caching, etc) often make them less-than-helpful on modern machines when compared to regular arrays. Also, even though mwpfh nodes can contain a fair bit of data overall, individual `SmartLists`s usually don't have that many elements.\r\n\r\nStill, it might be worth profiling.\r\n\r\nThere is a broader question of making nodes aware of their parent and siblings. I can see some use cases for that."}}