Skip to content

C
ccan
Switch branch/tag
  1. 12 Oct, 2018 3 commits
  3. 27 Sep, 2018 1 commit
  5. 26 Sep, 2018 1 commit
  7. 17 Sep, 2018 2 commits
  9. 23 Aug, 2018 1 commit
  11. 10 Aug, 2018 1 commit
  13. 27 Jul, 2018 5 commits
    • Rusty Russell's avatar
      tal/str: always create strings which have tal_count() == strlen() + 1. · 55d81423
      Rusty Russell authored 
      This is least-surprise, but also means callers can sometimes do faster
string handling by avoiding strstr().
Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      55d81423
    • Rusty Russell's avatar
      ccan/tal: always include a length field. · 1651e25e
      Rusty Russell authored 
      The current semantics of tal_count() / tal_bytelen() are to return 0
for anything not allocated using tal_arr*.  This is because we tried
to save a native-length word in the header, but produces an awkward
API.

(To make it worse, defining CCAN_TAL_DEBUG turns length to always on,
and we enable that for c-lightning developer mode, which hides bugs!).

However, for c-lightning, just over half of allocations want a length:
these use 3 words each, so we're actually worse off overall.

The answer is to always have a length field in the header.  This also
simplfies the tal code.

samba-allocs stats before:
Tal time: 1237102-1305755(1.251e+06+/-2.1e+04)ns
Tal_free time: 1346871-1514514(1.37844e+06+/-5.2e+04)ns

After:
Tal time: 1115180-1180633(1.1351e+06+/-2.1e+04)ns
Tal_free time: 1334381-1465933(1.39148e+06+/-4.7e+04)ns
Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      1651e25e
    • Rusty Russell's avatar
      tal/str and tal/stack: use _label interfaces. · 38ec541c
      Rusty Russell authored 
      In particular, tal/str now passes through the label from the caller,
so (in case of CCAN_TAL_DEBUG) you can actually see the file and line
where the caller was, not just inside ccan/str.
Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      38ec541c
    • Rusty Russell's avatar
      tal: add _label interfaces. · ed39cbbd
      Rusty Russell authored 
      There are a number of other utilities which use the tal_alloc_ and
tal_dup_arr_ internal interfaces directly, because they want to set
the label themselves.  We're about to break them all by changing those
internal interfaces, so give them a mid-level interface to use.
Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      ed39cbbd
    • Rusty Russell's avatar
      tal: rename tal_len to tal_bytelen. · 2cd5e81d
      Rusty Russell authored 
      I had a bug caused by using tal_len instead of tal_count: let's make
it explicit. @jb55 commented "ha. I always forget which one does which... Ack"
Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      2cd5e81d
  15. 04 Jul, 2018 1 commit
  17. 18 Jun, 2018 1 commit
  19. 12 Jun, 2018 10 commits
  21. 10 May, 2018 1 commit
  23. 09 May, 2018 2 commits
  25. 06 Apr, 2018 3 commits
  27. 05 Apr, 2018 2 commits
  29. 26 Mar, 2018 6 commits
    • Rusty Russell's avatar
      intmap: add iterator-by-callback. · 1e888a93
      Rusty Russell authored 
      It's significantly faster because it assumes no deletion:

10000000,critbit iteration (nsec),316
10000000,critbit callback iteration (nsec),90
...
10000000,critbit consecutive iteration (nsec),308
10000000,critbit consecutive callback iteration (nsec),78
Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      1e888a93
    • Rusty Russell's avatar
      intmap: add exhaustive testcases for intmap_after · a241664c
      Rusty Russell authored 
      We can't do the full range, but we can for a handful of bits (8).
Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      a241664c
    • 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
GitLab Nexedi Edition | About GitLab | About Nexedi | 沪ICP备2021021310号-2 | 沪ICP备2021021310号-7