On Mar 10, 2017, Richard Biener <richard.guent...@gmail.com> wrote: >>> So - if we fix this can we fix it by properly sorting things?
>> I don't see a way to do better, considering there's no real ID we could >> use for sorting. Do you? > Just use the ID you use but instead of maintaining a hash-map and traverse > that collect work items from the other hash-table into a vec and then sort > after the ID. Why is that better? You wrote 'hash-map' again, so I won't assume it was a mistake any more. I'm using a map for the seqno-to-chain mapping; that's a lot more predictable performance- and size-wise. Iterating over a hashmap requires one to go over all of the holes, and you get shuffled results that you then have to sort every time you'll iterate over the entries. You may have to do so multiple times, and if the number of chains is large (is that relevant in practice?) you may have to resize it multiple times. Whereas with the map I proposed, we always insert at the end, we iterate efficiently without having to do additional sorting, we most often remove from the head, and in the exceptional aliasing cases in which we remove from the middle, we do so without much regard to the element count. Now, if there's something you dislike about maps, we could make it a doubly-linked list, or maybe even a singly-linked list. I could replace seqno with a pointer to the next entry in the seq list. We'd just have to keep a pointer to the first entry instead of the newly-added map. We don't even need a pointer to the last element: we could make it work like a stack, rather than a queue, since the sequence of elements doesn't matter much, as long as we make it consistent. That would amount to more boilerplace list-maintenance code, but it's certainly doable, it costs just a pointer vs an int in the chains and an additional pointer over your suggestion, but it saves the shuffling and sorting. > I was just thinking that if we're going all the way of having IDs then > walking a hash-map of those IDs is not as good as we can do > with similar cost? You seem to consider walking a hash_map (which we did before) pretty costly, but then I'm not proposin us to do so; the performance features of a map are not the same as those of a hash_map, and I was proposing a map. Please reassess under this light, and considering the revised suggestion above. -- Alexandre Oliva, freedom fighter http://FSFLA.org/~lxoliva/ You must be the change you wish to see in the world. -- Gandhi Be Free! -- http://FSFLA.org/ FSF Latin America board member Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer
