Ok. Here's a crude demo in case someone is interested in doing benchmarking comparisons or whatever. The program is pure C, tested on linux 64-bit. Give two arguments: Nkeys and Filename. File should contain sym-value pairs, both unique in their domains. (Space-separated, one pair per line).
Update. Some additional notes regarding the program.
Portability is easily improved upon:
- Replace mmap/mremap with malloc/realloc. This is trivial.
- The test for direct vs indirect entries (ss offset) might be written as !(s->o >> 56), avoiding issues with endianness.
There are at least two bugs to fix:
- Verify sym to val loop has no test for NULL; this will fault on a missing key.
- The fetch_by_key should not proceed with a memcmp in case keylen > 8, but the slot is direct (ie <= 8).
Many further optimizations to consider:
- Try to allocate ss strings so that cache-line boundaries aren't crossed.
- Terminate strings with a high-bit: more compact, plus faster than using memchr.
- Specific inlined implementations for 8-byte memcmp, etc.
- Inplace reorder looks up every key twice. Place an (un)processed flag to halve this.
- Choose a faster hash function for string keys, FNV perhaps.
- A primitive hash function for values. Just a mul by constant?
There's also a wishlist for the CMPH library, but enough for now.
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
| |
For: |
|
Use: |
| & | | & |
| < | | < |
| > | | > |
| [ | | [ |
| ] | | ] |
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.