Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Reimplement NamedTuble#fetch(String) using a Trie #3174

Closed
wants to merge 1 commit into from

Conversation

lbguilherme
Copy link
Contributor

@lbguilherme lbguilherme commented Aug 19, 2016

Instead of comparing each string key one by one, build a Prefix Tree at compile-time and make a single comparison per char. This improves performance by 16x on large named tuples and about 1.5x on smaller ones.

Large benchmark: https://gist.github.com/lbguilherme/c7249c408d2a226bdbb6892dda5e9ab2
Small benchmark: https://gist.github.com/lbguilherme/7dba63104c4b44d3adcd5bcc9f9d7c20

See #3143 and #2966

Instead of comparing each string key one by one, build a Prefix Tree at compile-time and make a single comparison per char. This improves performance by 16x on large named tuples and about 1.5x on smaller ones.
@bcardiff
Copy link
Member

bcardiff commented Aug 19, 2016

I like this 👍 . Since you have a branch in the logic for more than 16 keys of the same size I would say we need some specs to cover that. Just to be sure it does not break in the future.

Let's see if some else agree with this before.

@asterite
Copy link
Member

I'm not sure about this, a named tuple is not to be used as a hash. They represent named arguments, to a method, and methods usually don't have many arguments. I'd rather have a short and simple implementation, even if a bit slower, than a complex, macro heavy one.

I'd need to find a real use case where big named tuples are used, and indexed with an arbitrary key.

@straight-shoota
Copy link
Member

If you have such a big datastructure, I don't see a point in using a NamedTuple as well.
A Hash has about the same lookup speed anyway, in this example it's even faster. But I had to cut down the number of entries in the NamedTuple since the compiler maxes at 300.

check every key   2.99  (334.04ms) (±24.93%) 341.02× slower
    trie lookup  34.87  ( 28.68ms) (± 9.12%)  29.28× slower
           hash   1.02k (979.55µs) (±11.60%)        fastest

https://gist.github.com/straight-shoota/cb903575c6dd86d1c6c86c372d842666

@akzhan
Copy link
Contributor

akzhan commented Jun 28, 2017

NamedTuple looks like returning value pattern, and eats less memory afair.

No more.

@asterite
Copy link
Member

Closing because too complex, and NamedTuple shouldn't normally be used.

@asterite asterite closed this Sep 29, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

5 participants