1. 08 Nov, 2010 10 commits
    • Rusty Russell's avatar
    • Rusty Russell's avatar
      iscsi: new module from Ronnie. · cb522f25
      Rusty Russell authored
      cb522f25
    • Rusty Russell's avatar
      htable: push capacity limit from 66 to 75% · 0473813a
      Rusty Russell authored
      With the extra bits, long runs don't hurt our cache very much on search,
      so we can pack quite a few in.  Here are the runs at maximal density before
      and after:
      
      Before:
      $ ./speed 3145000
      Initial insert:  248 ns
      Details: hash size 4194304, mask bits 9, perfect 63%
      Initial lookup (match):  122 ns
      Initial lookup (miss):  142 ns
      Initial lookup (random):  170 ns
      Initial delete all:  134 ns
      Details: rehashes 3145000
      Initial re-inserting:  149 ns
      Deleting first half:  73 ns
      Details: rehashes 1572500, delete markers 1572500
      Adding (a different) half:  128 ns
      Details: delete markers 0, perfect 62%
      Lookup after half-change (match):  129 ns
      Lookup after half-change (miss):  145 ns
      Details: initial churn
      Churning second time:  703 ns
      Churning third time:  725 ns
      Churning fourth time:  717 ns
      Churning fifth time:  710 ns
      Details: reinserting with spread
      Details: delete markers 149261, perfect 57%
      Details: worst run 254 (2 deleted)
      Lookup after churn & spread (match):  132 ns
      Lookup after churn & spread (miss):  159 ns
      Lookup after churn & spread (random):  184 ns
      Deleting half after churn & spread:  71 ns
      Adding (a different) half after churn & spread:  129 ns
      Details: delete markers 0, perfect 62%
      
      After:
      $ ./speed 3145727
      Initial insert:  232 ns
      Details: hash size 4194304, mask bits 9, perfect 63%
      Initial lookup (match):  122 ns
      Initial lookup (miss):  141 ns
      Initial lookup (random):  234 ns
      Initial delete all:  129 ns
      Details: rehashes 3145727
      Initial re-inserting:  153 ns
      Deleting first half:  80 ns
      Details: rehashes 1572864, delete markers 1572864
      Adding (a different) half:  137 ns
      Details: delete markers 0, perfect 62%
      Lookup after half-change (match):  125 ns
      Lookup after half-change (miss):  145 ns
      Details: initial churn
      Churning second time:  702 ns
      Churning third time:  719 ns
      Churning fourth time:  712 ns
      Churning fifth time:  709 ns
      Details: reinserting with spread
      Details: delete markers 169474, perfect 56%
      Details: worst run 248 (12 deleted)
      Lookup after churn & spread (match):  129 ns
      Lookup after churn & spread (miss):  159 ns
      Lookup after churn & spread (random):  242 ns
      Deleting half after churn & spread:  70 ns
      Adding (a different) half after churn & spread:  133 ns
      Details: delete markers 0, perfect 62%
      
      0473813a
    • Rusty Russell's avatar
      htable: restore perfect bit when resizing. · d3104024
      Rusty Russell authored
      If the lower bit differs between pointers, we can lose our "perfect"
      bit.  Since we're rehashing the entire thing anyway, we can pick
      another bit when we double the hash table.
      d3104024
    • Rusty Russell's avatar
      htable: use "perfect" bit to reduce rehashes. · 78e983a7
      Rusty Russell authored
      Steal one bit to indicate an entry is in its perfect position.  This
      means we don't have to rehash it when we are rehashing the entire
      table to get rid of deleted records, and we can still use it for
      comparison during lookup.
      
      Before: $ ./speed 50000000
      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%
      
      After:
      Initial insert:  467 ns
      Details: hash size 134217728, mask bits 5, perfect 81%
      Initial lookup (match):  163 ns
      Initial lookup (miss):  171 ns
      Initial lookup (random):  326 ns
      Initial delete all:  170 ns
      Details: rehashes 50000000
      Initial re-inserting:  169 ns
      Deleting first half:  88 ns
      Details: rehashes 25000000, delete markers 25000000
      Adding (a different) half:  141 ns
      Details: delete markers 0, perfect 81%
      Lookup after half-change (match):  166 ns
      Lookup after half-change (miss):  171 ns
      Details: initial churn
      Churning second time:  441 ns
      Churning third time:  469 ns
      Churning fourth time:  466 ns
      Churning fifth time:  490 ns
      Details: reinserting with spread
      Details: delete markers 13800468, perfect 73%
      Details: worst run 48 (4 deleted)
      Lookup after churn & spread (match):  197 ns
      Lookup after churn & spread (miss):  209 ns
      Lookup after churn & spread (random):  369 ns
      Deleting half after churn & spread:  98 ns
      Adding (a different) half after churn & spread:  100 ns
      Details: delete markers 29539689, perfect 72%
      78e983a7
    • 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