encoding_rs icon indicating copy to clipboard operation
encoding_rs copied to clipboard

Convert sorted data arrays to the Eytzinger order

Open hsivonen opened this issue 7 years ago • 3 comments

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.

hsivonen avatar Jun 24 '17 09:06 hsivonen

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

jrmuizel avatar Oct 26 '17 05:10 jrmuizel

Thank you. I hadn't seen it.

hsivonen avatar Oct 26 '17 07:10 hsivonen

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 avatar Dec 18 '18 08:12 hsivonen