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

Convert sorted data arrays to the Eytzinger order #20

Open
hsivonen opened this issue Jun 24, 2017 · 3 comments
Open

Convert sorted data arrays to the Eytzinger order #20

hsivonen opened this issue Jun 24, 2017 · 3 comments

Comments

@hsivonen
Copy link
Owner

The Eytzinger order improved things for Gecko's HTML parser. Data tables that are currently only searched by binary search should probably be converted to the Eytzinger order.

@jrmuizel
Copy link

Not sure if you saw this or not but here's rust implementation of Eytzinger-arranged arrays: https://github.com/jonhoo/ordsearch

@hsivonen
Copy link
Owner Author

Thank you. I hadn't seen it.

@hsivonen
Copy link
Owner Author

I'll leave this open in case someone else really cares enough to implement and measure, but

  • The hot part of EUC-KR has to remain in its present order.
  • Re-sorting the cold parts of EUC-KR and GBK probably doesn't matter much as they are cold parts.
  • The label lookup is probably fast enough as-is not to merit active effort on it.

@hsivonen hsivonen changed the title Converted sorted data arrays to the Eytzinger order Convert sorted data arrays to the Eytzinger order Nov 2, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants