1. 26 Mar, 2018 5 commits
    • Rusty Russell's avatar
      intmap: add test case which failed, extracted from real world usage. · 4d9c7e1c
      Rusty Russell authored
      Because intmap_after_() would simply examine the critbits to walk the
      tree, it wouldn't realize that it might be in the completely wrong tree.
      
      In this case:
      
               Bit 4:
               0   1
              /     \
             /       \
        100000011  100001011
      
      When we ask for intmap_after_(011111111) we would check the critbit, it's
      a 1, so we end up on the right leaf instead of the left.
      Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      4d9c7e1c
    • Rusty Russell's avatar
      intmap: reimplement so that intmap_after works. · e59acd52
      Rusty Russell authored
      A critbit tree is a binary tree which keeps branches for each bit
      which differs in the leaves.  It's a simple data structure, but not
      entirely simple to implement the primitives people expect, as this bus
      shows.
      
      The bug: I added an open iterator, and intmap_after_ for a random
      value would sometimes return the wrong node.
      
      Cause: we don't know what the prefix is as we iterate, so by only
      testing the critbits in the tree, we can end up in the wrong place.
      This is only a problem if the value isn't in the (sub)tree, but this
      can easily happen even with contiguous trees should deletion occur.
      You can see an example in the next patch, which adds a test.
      
      After finding a bug in my intmap_after() routine, I went searching for
      other implementations to see how they handled it.  Most didn't provide
      an open-ended iterator like this, relying on callback iterators which
      don't allow deletion.  Gah!
      
      The exception was https://github.com/blynn/blt/blob/master/blt.c#L179
      which implements blt_ceil() which does this (if you add one to the
      key, at least).  However, it does it by effectively finding a node,
      using that to derive the prefix, then walking down the tree again.
      That's pretty suboptimal.
      
      There are basically two choices if you want an efficient after()
      operation: to reimplement this approach with some optimizations
      (ie. keep branches as we descend, and when we get to the bottom and
      know the prefix, we know which branch to go down), or keep the bits
      which got to each node.
      
      The latter is more optimal, but less generally useful: for bit
      strings, for example, we could keep the bits in common on each node,
      rather than storing the entire string at the bottom.  But in practice
      you'd be doing allocations to re-create the index if the caller wanted
      it.
      
      However, in this implementation our keys are 64 bits only, and we
      already use a u8 for the bit number: using a 64-bit value there
      consumes no more space (thanks to alignment).  We can store the
      critbit by using the prefix capped by a bit: 0b10000...0000 means
      no prefix and highest bit is the critbit, and 0bxxxxx1000...000
      means the prefix is xxxxxx and the critbit is the 6th highest bit.
      
      The penalty is that iteration 70% slower.  It's still pretty fast
      though.
      
      Before:
      $ for i in `seq 5`; do ./speed 10000000; done | stats
      10000000,random generation (nsec),3-4(3.2+/-0.4)
      10000000,critbit insert (nsec),1530-1751(1633.2+/-80)
      10000000,critbit successful lookup (nsec),1723-1993(1806.8+/-97)
      10000000,critbit failed lookup (nsec),1763-2104(1933.6+/-1.3e+02)
      10000000,critbit iteration (nsec),208-266(242.2+/-19)
      10000000,critbit memory (bytes),48
      10000000,critbit delete (nsec),1747-1861(1803.8+/-42)
      10000000,critbit consecutive iteration (nsec),182-228(210+/-18)
      
      After:
      10000000,random generation (nsec),3-4(3.2+/-0.4)
      10000000,critbit insert (nsec),1533-1699(1628+/-65)
      10000000,critbit successful lookup (nsec),1831-2104(1972.4+/-1e+02)
      10000000,critbit failed lookup (nsec),1850-2152(2008.2+/-1.1e+02)
      10000000,critbit iteration (nsec),304-324(312.8+/-7.5)
      10000000,critbit memory (bytes),48
      10000000,critbit delete (nsec),1617-1872(1752+/-99)
      10000000,critbit consecutive iteration (nsec),303-318(311+/-5.4)
      Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      e59acd52
    • Rusty Russell's avatar
      intmap: add benchmarks. · 82229812
      Rusty Russell authored
      I wrote these a while ago, dig them out.
      
      On my laptop, min-max(avg+/-stdev) of 5 runs:
      
      make && for i in `seq 5`; do ./speed 10000000; done | stats
      make: Nothing to be done for 'all'.
      10000000,random generation (nsec),3-4(3.2+/-0.4)
      10000000,critbit insert (nsec),1530-1751(1633.2+/-80)
      10000000,critbit successful lookup (nsec),1723-1993(1806.8+/-97)
      10000000,critbit failed lookup (nsec),1763-2104(1933.6+/-1.3e+02)
      10000000,critbit iteration (nsec),208-266(242.2+/-19)
      10000000,critbit memory (bytes),48
      10000000,critbit delete (nsec),1747-1861(1803.8+/-42)
      10000000,critbit consecutive iteration (nsec),182-228(210+/-18)
      10000000,hash insert (nsec),396-424(412+/-9.6)
      10000000,hash successful lookup (nsec),150-164(157.4+/-5.5)
      10000000,hash failed lookup (nsec),163-178(170+/-5.5)
      10000000,hash iteration (nsec),21-26(23.2+/-1.7)
      10000000,hash memory (bytes),45
      10000000,hash delete (nsec),179-194(183.6+/-5.3)
      Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      82229812
    • Rusty Russell's avatar
      bitops: new module. · eb10bf9f
      Rusty Russell authored
      Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      eb10bf9f
    • Rusty Russell's avatar
  2. 16 Mar, 2018 1 commit
    • Jan Sarenik's avatar
      Makefile: Fix asort multiple definition error · 7a75cff7
      Jan Sarenik authored
      Error I experienced on Alpine Linux without this patch:
      
          In file included from ccan/generator/generator.c:8:0:
          ./ccan/generator/generator.h:23:2: error: #error Generators require coroutines
           #error Generators require coroutines
            ^~~~~
          make: *** [Makefile:32: ccan/generator/generator.o] Error 1
      7a75cff7
  3. 14 Mar, 2018 2 commits
  4. 01 Mar, 2018 1 commit
  5. 26 Feb, 2018 2 commits
  6. 16 Feb, 2018 1 commit
  7. 04 Feb, 2018 1 commit
  8. 21 Dec, 2017 1 commit
  9. 22 Nov, 2017 1 commit
  10. 25 Oct, 2017 1 commit
  11. 12 Oct, 2017 2 commits
  12. 11 Oct, 2017 1 commit
  13. 12 Sep, 2017 1 commit
  14. 04 Sep, 2017 2 commits
  15. 29 Aug, 2017 3 commits
  16. 15 Aug, 2017 2 commits
  17. 23 Jul, 2017 4 commits
  18. 27 Jun, 2017 1 commit
  19. 16 Jun, 2017 1 commit
  20. 31 May, 2017 1 commit
    • Rusty Russell's avatar
      io: fix nasty io_wake corner case. · d00c9d1b
      Rusty Russell authored
      If we're duplex and one io_always callback makes the other io_always,
      we screwed up and hit an assertion later when the conn was in the
      always list but didn't actually want to be.
      
      io_wake() uses io_always(), so this is how it happened.  Writing a
      test case for this was a bit fun, too.
      Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      d00c9d1b
  21. 05 Apr, 2017 6 commits