1. 08 Nov, 2010 5 commits
    • Rusty Russell's avatar
      htable: rehash to clear delete markers · 6ceee268
      Rusty Russell authored
      Delete markers build up over time, even if we try to clean as we go.
      So just garbage collect them when there are too many.
      
      Before:
      rusty@vivaldi:~/devel/cvs/ccan/ccan/htable/tools (htable)$ ./speed 50000000
      Initial insert:  467 ns
      Details: hash size 134217728, mask bits 5, perfect 81%
      Initial lookup (match):  160 ns
      Initial lookup (miss):  169 ns
      Initial lookup (random):  328 ns
      Initial delete all:  165 ns
      Details: rehashes 50000000
      Initial re-inserting:  317 ns
      Deleting first half:  86 ns
      Details: rehashes 25000000, delete markers 25000000
      Adding (a different) half:  89 ns
      Details: delete markers 18894324, perfect 76%
      Lookup after half-change (match):  174 ns
      Lookup after half-change (miss):  203 ns
      Details: initial churn
      Churning second time:  816 ns
      Churning third time:  615 ns
      Churning fourth time:  621 ns
      Churning fifth time:  846 ns
      Details: reinserting with spread
      Details: delete markers 11078719, perfect 74%
      Details: worst run 48 (4 deleted)
      Lookup after churn & spread (match):  191 ns
      Lookup after churn & spread (miss):  208 ns
      Lookup after churn & spread (random):  374 ns
      Deleting half after churn & spread:  102 ns
      Adding (a different) half after churn & spread:  103 ns
      Details: delete markers 27442234, perfect 73%
      
      After:
      Initial insert:  462 ns
      Details: hash size 134217728, mask bits 5, perfect 81%
      Initial lookup (match):  161 ns
      Initial lookup (miss):  168 ns
      Initial lookup (random):  326 ns
      Initial delete all:  164 ns
      Details: rehashes 50000000
      Initial re-inserting:  167 ns
      Deleting first half:  86 ns
      Details: rehashes 25000000, delete markers 25000000
      Adding (a different) half:  217 ns
      Details: delete markers 0, perfect 81%
      Lookup after half-change (match):  169 ns
      Lookup after half-change (miss):  180 ns
      Details: initial churn
      Churning second time:  593 ns
      Churning third time:  611 ns
      Churning fourth time:  619 ns
      Churning fifth time:  622 ns
      Details: reinserting with spread
      Details: delete markers 13800468, perfect 73%
      Details: worst run 48 (4 deleted)
      Lookup after churn & spread (match):  192 ns
      Lookup after churn & spread (miss):  211 ns
      Lookup after churn & spread (random):  373 ns
      Deleting half after churn & spread:  103 ns
      Adding (a different) half after churn & spread:  102 ns
      Details: delete markers 29539689, perfect 72%
      6ceee268
    • Rusty Russell's avatar
      htable: speed benchmark · ee0e05e4
      Rusty Russell authored
      ee0e05e4
    • Rusty Russell's avatar
      htable: first implementation · 198d85ad
      Rusty Russell authored
      198d85ad
    • Rusty Russell's avatar
      jmap: a speed benchmark · b84d624e
      Rusty Russell authored
      b84d624e
    • Rusty Russell's avatar
      d086611e
  2. 07 Nov, 2010 3 commits
  3. 04 Nov, 2010 8 commits
  4. 03 Nov, 2010 13 commits
  5. 02 Nov, 2010 1 commit
  6. 30 Oct, 2010 3 commits
  7. 29 Oct, 2010 1 commit
  8. 27 Oct, 2010 1 commit
  9. 26 Oct, 2010 5 commits