[dmd-internals] [D-Programming-Language/dmd] 093a4b: faster StringTable

[GitHub via dmd-internals]

  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 at 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 at 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 at 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 at 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 at 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 at 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 at 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