October 23, 2014 [dmd-internals] [D-Programming-Language/dmd] 093a4b: faster StringTable | ||||
---|---|---|---|---|
| ||||
Attachments:
| Branch: refs/heads/master Home: https://github.com/D-Programming-Language/dmd Commit: 093a4b53f1e113e5209c9cd619fee7c707cecfe7 https://github.com/D-Programming-Language/dmd/commit/093a4b53f1e113e5209c9cd619fee7c707cecfe7 Author: Martin Nowak <code@dawg.eu> Date: 2014-10-22 (Wed, 22 Oct 2014) Changed paths: M src/root/stringtable.c M src/root/stringtable.h Log Message: ----------- faster StringTable - use a hash table with open addressing and linear probing for better cache locality Commit: 256878f980f0542ad4f5ac85bdcb2516c81fe78d https://github.com/D-Programming-Language/dmd/commit/256878f980f0542ad4f5ac85bdcb2516c81fe78d Author: Martin Nowak <code@dawg.eu> Date: 2014-10-22 (Wed, 22 Oct 2014) Changed paths: M src/lexer.c M src/libelf.c M src/libmach.c M src/libmscoff.c M src/libomf.c M src/mtype.c M src/root/stringtable.c M src/traits.c Log Message: ----------- reserve enough initial capacity to avoid hash table resizes - based on numbers from phobos compilation Commit: 20070855fe88b58664dd678cfa45cfc18093c9bf https://github.com/D-Programming-Language/dmd/commit/20070855fe88b58664dd678cfa45cfc18093c9bf Author: Martin Nowak <code@dawg.eu> Date: 2014-10-24 (Fri, 24 Oct 2014) Changed paths: M src/root/stringtable.c Log Message: ----------- use triangular numbers for probing - guaranteed to visit every bucket in a power of 2 sized hash table - mitigates clustering problem (with many hash collisions) while still preserving good cache locality Commit: a569229bf8298eeb03e247b358854833c60f25be https://github.com/D-Programming-Language/dmd/commit/a569229bf8298eeb03e247b358854833c60f25be Author: Martin Nowak <code@dawg.eu> Date: 2014-10-24 (Fri, 24 Oct 2014) Changed paths: M src/root/stringtable.c Log Message: ----------- use MurmurHash2 - much better distribution leads to less collisions and thus to faster lookup - also faster Commit: ee7d8d7d24c0382a916cb07d3cc3e9f073b6161b https://github.com/D-Programming-Language/dmd/commit/ee7d8d7d24c0382a916cb07d3cc3e9f073b6161b Author: Martin Nowak <code@dawg.eu> Date: 2014-10-24 (Fri, 24 Oct 2014) Changed paths: M src/root/stringtable.c M src/root/stringtable.h Log Message: ----------- reduce StringEntry size from 16 to 8 byte - more cache hits - allocate StringValues from pools in StringTable and reference them with a 32-bit index+offset - hash was only 32-bit anyhow so use uin32_t instead of hash_t Commit: 0726d75f8901bb3eee4b18178da4758e9bc15d73 https://github.com/D-Programming-Language/dmd/commit/0726d75f8901bb3eee4b18178da4758e9bc15d73 Author: Martin Nowak <code@dawg.eu> Date: 2014-10-24 (Fri, 24 Oct 2014) Changed paths: M src/root/stringtable.c M src/root/stringtable.h Log Message: ----------- StringEntry as POD - call getValue(vptr) in findSlot only when hash matches (saves a possibly unnecessary load) Commit: 047d0de680c32f5b7ce746e6de574698898535b7 https://github.com/D-Programming-Language/dmd/commit/047d0de680c32f5b7ce746e6de574698898535b7 Author: Walter Bright <walter@walterbright.com> Date: 2014-10-23 (Thu, 23 Oct 2014) Changed paths: M src/lexer.c M src/libelf.c M src/libmach.c M src/libmscoff.c M src/libomf.c M src/mtype.c M src/root/stringtable.c M src/root/stringtable.h M src/traits.c Log Message: ----------- Merge pull request #4088 from MartinNowak/fasterStringTable faster string table Compare: https://github.com/D-Programming-Language/dmd/compare/76cb58b3fe56...047d0de680c3 |
Copyright © 1999-2021 by the D Language Foundation