Engineering Faster Sorters for Small Sets of Items | Hacker News Reader

Engineering Faster Sorters for Small Sets of Items

arxiv.org

38 pointsmatt_d9 comments

In the similar topic, I'm trying to find maps optimised for a small maximum number of items (8 or 16) indexed by integers. Curiously I failed to find discussions about this topic.. But std::map seems very badly fit for this kind of map.

Perhaps it's worth considering succinct data structures (https://en.wikipedia.org/wiki/Succinct_data_structure), e.g.:

- BitMagic: http://bitmagic.io/, https://github.com/tlk00/BitMagic

- Succinct Data Structure Library 2.0: https://github.com/simongog/sdsl-lite, https://github.com/simongog/sdsl-lite/wiki/Literature

Thanks but these structures are size optimised, I'm looking for CPU usage optimised structures.

Does this sound interesting: http://llvm.org/docs/ProgrammersManual.html#llvm-adt-indexed... http://llvm.org/doxygen/IndexedMap_8h_source.html

I will have a look thanks. I think I'll implement it with two arrays one for keys one for values and a loop to find the key index, then return the corresponding value It may be better to fully unroll the loop, I'll have to benchmark this. SSE may be interesting too.

The most interesting thing to me is "the compiler reduces its optimizations with increasing compilation effort, when compiling only a single source file." Is this GCC-specific, or does it also hold for clang? And can it be tuned away?

Clang will not "reduce compilation effort" and I do not believe GCC does that. There are heuristics that look at things like function size but I don't think that is what they mean. Generally speaking, translation units are independent if you do not run link-time-optimizations (LTO) and optimizations follow a (basically) predetermined order which might be influence by the input but not by the amount of work done.

I’ve never heard of or experienced gcc using some kind of cost model for compilation time, either. With all these huge protobuf-generated files you’d think I would have noticed if it existed.

Love papers like this, hyper-focused on a fun problem and then full of hacks.

Reply on news.ycombinator.com