isPermutationBy is unnecessarily slow

[treeowl]

Currently, the equality test converts arrays to lists and then uses isPermutationBy to check whether one is a permutation of the other. This seems even more wasteful than necessary. Here's a general plan for performing the test more quickly:

1. Check that the lengths match
2. Thaw one of the arrays (safely). This should be less than half the allocation required to convert a single array to a list.
3. Walk over the unthawed array. For each element:
   a. Search for the matching one in the thawed array.
   b. If it's found, (conceptually) perform an element swap to align it with its match. In fact, the element itself can be discarded, leaving an undefined element aligned with the match.

[tibbe]

I'm open for pull requests! (Also I probably need a co-maintainer at some point, given that I'm not very involved with Haskell anymore).

[treeowl]

I'd be happy to co-maintain, but I'd need proper documentation of the data structure and its invariants first. The linked paper doesn't seem sufficient (for me). Do you think you can help with that?

…

On Jun 12, 2017 9:49 PM, "Johan Tibell" ***@***.***> wrote: I'm open for pull requests! (Also I probably need a co-maintainer at some point, given that I'm not very involved with Haskell anymore). — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#155 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_XfSUlIdsOO63fzYvH0yFt5gg1BVks5sDdhNgaJpZM4N3lms> .

[tibbe]

Yes. Let me try to put some developer docs together the next few days.

[treeowl]

Thanks! On Jun 12, 2017 11:56 PM, "Johan Tibell" <notifications@github.com> wrote: Yes. Let me try to put some developer docs together the next few days. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#155 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_Us_yOgYRsO5fl7-V9IdZMLNx9rBks5sDfZfgaJpZM4N3lms> .

[phadej]

@treeowl out of curiosity, do you have a real world case where there is a lot of collisions (i.e. Collision nodes are e.g. >= 3 in length)? Or is it more "let's make it fast, because it seems to be slow". I'm 👍 for optimising, but not sure if we can have realistic benchmark (which we should!)

[treeowl]

No, just the "wait, we're doing WHAT?" feeling.

…

On Jun 13, 2017 3:49 AM, "Oleg Grenrus" ***@***.***> wrote: @treeowl <https://github.com/treeowl> out of curiosity, do you have a real world case where there is a lot of collisions (i.e. Collision nodes are e.g. >= 3 in length)? Or is it more "let's make it fast, because it seems to be slow". I'm 👍 for optimising, but not sure if we can have realistic benchmark (which we should!) — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#155 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_Uojg_ytgC22TCmdxQE5IIXfO4WBks5sDj8hgaJpZM4N3lms> .

[tibbe]

@treeowl I've added some initial docs in https://github.com/tibbe/unordered-containers/blob/master/docs/developer-guide.md and added you as a contributor.

Since I'm way to familiar to the code base to know what needs to be documented, please let me know what would be helpful.

[sjakobi]

3. Walk over the unthawed array. For each element:
a. Search for the matching one in the thawed array.
b. If it's found, (conceptually) perform an element swap to align it with its match. In fact, the element itself can be discarded, leaving an undefined element aligned with the match.

For reference: #291 is a similar optimization.