1. 16 Jun, 2019 1 commit
  2. 14 Jun, 2019 1 commit
  3. 27 Feb, 2019 1 commit
  4. 22 Aug, 2018 1 commit
  5. 21 Aug, 2018 1 commit
    • Oleg Kolosov's avatar
      Use feature test macro for aligned_alloc · 39c3038c
      Oleg Kolosov authored
      Reorder ifdef checks in BTreeImpl::growTree to make posix_memalign the
      default case and hide aligned_alloc behind feature test macro. This
      covers more systems and actually fixes the compatibility with Android.
      39c3038c
  6. 19 Aug, 2018 1 commit
  7. 05 Aug, 2018 10 commits
    • Kenton Varda's avatar
      Apply @harrishancock review comments. · 62beedb5
      Kenton Varda authored
      62beedb5
    • Kenton Varda's avatar
      Optimize hash table modulus operation using big switch. · 25a25704
      Kenton Varda authored
      Integer division is really, really slow. The integer hash table benchmark spends most of its time in modulus operations!
      
      This change shaves 32% off the integer hash table benchmark runtime, and 8% off the string hash table benchmark runtime.
      25a25704
    • Kenton Varda's avatar
    • Kenton Varda's avatar
      Sadly, MSVC cannot handle pointer-to-members in constexprs. · 5cd3e108
      Kenton Varda authored
      This is true even if the pointer-to-member is never actually used, but only has its type matched, which was what kj::size() was trying to do.
      
      Oh well, define some damned constants instead.
      5cd3e108
    • Kenton Varda's avatar
      Implement lg() for MSVC. · b299dcd7
      Kenton Varda authored
      b299dcd7
    • Kenton Varda's avatar
      Fix some MSVC problems. · 0117595a
      Kenton Varda authored
      0117595a
    • Kenton Varda's avatar
      5eeb125b
    • Kenton Varda's avatar
      Fix typos spotted by @zarvox. · 2709adb4
      Kenton Varda authored
      2709adb4
    • Kenton Varda's avatar
      Add IntertionOrderIndex. · 4a330282
      Kenton Varda authored
      4a330282
    • Kenton Varda's avatar
      Implement kj::Table, an alternative to STL maps/sets. · 8707e731
      Kenton Varda authored
      Hash-based (unordered) and tree-based (ordered) indexing are provided.
      
      kj::Table offers advantages over STL:
      - A Table can have multiple indexes (allowing lookup by multiple keys). Different indexes can use different algorithms (e.g. hash vs. tree) and have different uniqueness constraints.
      - The properties on which a Table is indexed need not be explicit fields -- they can be computed from the table's row type.
      - Tables use less memory and make fewer allocations than STL, because rows are stored in a contiguous array.
      - The hash indexing implementation uses linear probing rather than chaining, which again means far fewer allocations and more cache-friendliness.
      - The tree indexing implementation uses B-trees optimized for cache line size, whereas STL uses cache-unfriendly and allocation-heavy red-black binary trees. (However, STL trees are overall more cache-friendly; see below.)
      - Most of the b-tree implementation is not templated. This reduces code bloat, at the cost of some performance due to virtual calls.
      
      On an ad hoc benchmark on large tables, the hash index implementation appears to outperform libc++'s `std::unordered_set` by ~60%. However, libc++'s `std::set` still outperforms the B-tree index by ~70%. It looks like the B-tree implementation suffers in part from the fact that keys are not stored inline in the tree nodes, forcing extra memory indirections. This is a price we pay for lower memory usage overall, and the ability to have multiple indexes on one table. The b-tree implementation also suffers somewhat from not being 100% templates, compared to STL, but I think this is a reasonable trade-off. The most performance-critical use cases will use hash indexes anyway.
      8707e731