sipa changed the topic of #bitcoin-wizards to: This channel is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
tjader has quit [Ping timeout: 276 seconds]
tjader has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 256 seconds]
nonaTure has quit [Quit: Leaving.]
Jeremy_Rand_2 has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
GGuyZ has quit [Read error: Connection reset by peer]
AndChat|435584 has joined #bitcoin-wizards
GGuyZ has joined #bitcoin-wizards
MrChrisJ_ has joined #bitcoin-wizards
skyraider_ has quit [Quit: Connection closed for inactivity]
MrChrisJ_ has quit [Client Quit]
MrChrisJ has quit [Ping timeout: 256 seconds]
GAit has quit [Quit: Leaving.]
RoboTedd_ has joined #bitcoin-wizards
RoboTeddy has quit [Ping timeout: 265 seconds]
memymo has joined #bitcoin-wizards
mkarrer_ has quit [Remote host closed the connection]
GAit has joined #bitcoin-wizards
dcousens has quit [Ping timeout: 264 seconds]
chjj has quit [Quit: null]
chjj has joined #bitcoin-wizards
chjj has quit [Client Quit]
tjader has quit [Ping timeout: 276 seconds]
chjj has joined #bitcoin-wizards
tjader has joined #bitcoin-wizards
markus-k_ has joined #bitcoin-wizards
mrkent has joined #bitcoin-wizards
markus-k_ has quit [Max SendQ exceeded]
voxelot has quit [Ping timeout: 240 seconds]
TheSeven has quit [Ping timeout: 240 seconds]
GGuyZ has quit [Quit: GGuyZ]
polyclef has quit [Ping timeout: 265 seconds]
roman has quit [Remote host closed the connection]
TheSeven has joined #bitcoin-wizards
bobke has joined #bitcoin-wizards
brg444 has quit [Quit: Page closed]
kang_ has joined #bitcoin-wizards
BananaLotus has quit [Remote host closed the connection]
guruvan has quit [Remote host closed the connection]
kefkius has quit [Remote host closed the connection]
arowser has quit [Quit: No Ping reply in 180 seconds.]
arowser has joined #bitcoin-wizards
Giszmo has quit [Ping timeout: 272 seconds]
alpalp has quit [Remote host closed the connection]
AaronvanW has quit [Read error: Connection reset by peer]
AaronvanW has joined #bitcoin-wizards
danielsocials has joined #bitcoin-wizards
danielsocials has quit [Remote host closed the connection]
memymo has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
GGuyZ has joined #bitcoin-wizards
alpalp has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
adam3us has joined #bitcoin-wizards
adam3us has quit [Client Quit]
adam3us has joined #bitcoin-wizards
funkenstein_ has joined #bitcoin-wizards
oneeman has joined #bitcoin-wizards
dnaleor has quit [Quit: Leaving]
GGuyZ has quit [Quit: GGuyZ]
kyletorpey has joined #bitcoin-wizards
Giszmo has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
Giszmo has quit [Ping timeout: 240 seconds]
kyletorpey has left #bitcoin-wizards [#bitcoin-wizards]
tjader has quit [Ping timeout: 276 seconds]
moa has quit [Quit: Leaving.]
tjader has joined #bitcoin-wizards
roconnor has joined #bitcoin-wizards
<gmaxwell> tromp_: CONGRATS ON L19 computation!
binns has joined #bitcoin-wizards
binns is now known as Guest19968
Guest19968 has quit [Changing host]
Guest19968 has joined #bitcoin-wizards
Guest19968 has joined #bitcoin-wizards
Guest19968 is now known as binns
GGuyZ has joined #bitcoin-wizards
Giszmo has joined #bitcoin-wizards
binns is now known as wbinns
wbinns is now known as binns
go1111111 has quit [Ping timeout: 260 seconds]
binns has quit [Quit: Updating details, brb]
binns has joined #bitcoin-wizards
go1111111 has joined #bitcoin-wizards
<tromp_> thanks, Gregory!
AaronvanW has quit [Ping timeout: 250 seconds]
arowser has quit [Quit: No Ping reply in 180 seconds.]
danielsocials has joined #bitcoin-wizards
arowser has joined #bitcoin-wizards
bityogi has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
<bsm1175321> Whazzat?
<bsm1175321> Darn. There goes my PoW algorithm...
<tromp_> perfect for a 9 month block interval:-)
<bsm1175321> Hey, if my landlord accepts yearly rent...
adam3us has quit [Quit: Leaving.]
<bsm1175321> I actually typed: isprime(2**74207281-1) into Maple today. Perhaps I was over-optimistic.
<bsm1175321> there must be special techniques for merseinne primes...
sCOGSBY has quit [Remote host closed the connection]
chjj_ has joined #bitcoin-wizards
gavink has quit [Ping timeout: 245 seconds]
<tromp_> i think it's called the lucas-lehmer test
chjj_ has quit [Quit: null]
bramc has joined #bitcoin-wizards
<bramc> Okay, so I'm partway into writing the insertion code now, and somewhat unrelatedly have run into a bit of a moral dilemma
dnaleor has quit [Quit: Leaving]
<bramc> For fairly obvious reasons it's much faster to check for inclusion in a hashtable than in a tree, so when doing significant inclusion checking operations it's a good idea to have a parallel standard set for doing those operations. Some goes if you want a map.
binns has quit [Quit: Updating details, brb]
<bramc> So there's this ridiculous is_included() method sitting here. On the one hand, someone might have a good reason for using it in case of emergency. On the other hand, it's inclusion would seem to imply that it's a good idea to use it. I'm tempted to remove it completely. What does everybody think?
binns has joined #bitcoin-wizards
<bsm1175321> You really want this fast, don't you?
<bsm1175321> log(n) vs O(1) is a good problem to have.
<bramc> The method is_included_make_proof() of course stays. The advantage of is_included() is that it's much more performant, but nowhere near as performant as the same call on a normal set is.
<bsm1175321> I'm wrestling with O(n^3) on some braid algorithms.
Guest75253 is now known as mr_burdell
o3u is now known as Fistful_of_Coins
mr_burdell has quit [Changing host]
mr_burdell has joined #bitcoin-wizards
<bramc> bsm117532 It's already log(n), The whole point of this exercise is to get cache misses from log(n) to log(log(n)). Constant factors matter.
funkenstein_ has left #bitcoin-wizards ["Leaving"]
<bramc> Technically log(log(n)) isn't a constant factor, but it acts a lot like it in practice.
<bsm1175321> Hashes should be O(1) no? You're probably using a more sophisticated analysis of the buckets than me...
<bramc> Yes hashes are O(1). It's my set which is O(log(log(n))
<bramc> )
<bsm1175321> Uh...How did you add another log?
<bramc> The location of nodes in memory is set up so that they're near each other.
<bramc> In the case of is_included() it skips to the bottom of a block directly thus avoiding a bunch of lookups, making its behavior much closer to that of a hashtable.
voxelot has joined #bitcoin-wizards
<bramc> At least, it does that for balanced blocks. Basically it's treating balanced blocks as hashtables, which is a fairly accurate description of them
<bsm1175321> So it's a binary tree, which is log(n) in general, or O(1) modulo bucket reallcation... Explain how memory locality is modifying this?
<bsm1175321> What is a "block" in this context?
<bramc> The fanout within a block is limited, it only goes so many levels deep before pointing to another block
danielsocials has quit [Remote host closed the connection]
<bsm1175321> I see, so the n of the block-based algorithm is log(n) for the blocks.
<bsm1175321> Wait, that can't work...
<bramc> So a block might represent, say, 5 bits. If you're doing a lookup at, say, 33 bits, you'll have cache misses at bits 4, 9, 14, 19, 24, 29, and then you're in a leaf so there are lookups for 30, 31, 32, and 33, but they're probably all in close memory proximity because they're in the same block.
<bsm1175321> The cache size shouldn't turn it from O(log(n)) to O(log(log n)) butt it might turn it into O((cache)*log(n/cache)), no?
NewLiberty has quit [Ping timeout: 250 seconds]
<bramc> My brain is too addled from writing 100 lines of code just now to make such subtle distinctions. There are ugly practicalities in this code.
<bsm1175321> I'm afraid you know a lot more about caches than me.
<bramc> The l1 and l2 cache are fairly simple. If you do a lookup to a place in memory too far from any of the places you've recently looked, you have to wait for it to be swapped into cache, which is fairly expensive.
<bramc> Some concept as disk accesses, but smaller distances and smaller times.
<bsm1175321> I guess my argument is that if you have an O(log(n)) algorithm (a binary tree), and you play caching games, this can't possibly get it to O(log(log(n))), can it? It can just insert funny constant factors, but not another log.
<bsm1175321> If I graphed it, it should be A*log(n) + B*log(n) + C*log(n) as n gets larget, with discrete jumps between A,B,C as the caches get full, no?
<bsm1175321> *larger
Burrito has quit [Quit: Leaving]
<bsm1175321> Jumps due to the speed of the caches.
<bramc> The tricks are that (a) branch blocks are in fixed position, so you can jump to the place where they point out most of the time, (b) everything within a block is in close proximity, so you can traverse the whole thing with possibly only a single cache miss
<bramc> I'm of course not directly referencing caches in my code. Just doing really weird-looking manual memory management to behave well with them.
<bramc> Mostly I have a giant byte array called self.memory
<bsm1175321> Shouldn't this just smooth out the transition between size(L1), size(L2), and size(L3) rather than make it log log?
<bsm1175321> I mean, the asymptotic limit, for a very large set, the cache doesn't help, no?
<bramc> Caches don't exactly get full. The simple model is to imagine that the computer has a small number of caches of fixed size: Say 16 of size 16 kilobytes, and whenever a part of memory is pulled in it's either part of one of the last 16 or the general neighborhood of size 16 kilobytes gets pulled into cache, and the least recently used gets booted.
<bramc> So if you can be very clever about making memory lookups have a lot of local affinity things can be very fast. Tree operations tend to bottleneck on waiting for memory.
<bsm1175321> I'd think it would be e.g. B*log(n/b) to find the block plus A*log(n/a) within the bloc, for example, for an overall B*log(n/b) + A*log(n/a) = (A+B)*log(n) - B log b - A log a...
<bsm1175321> So the cache is adding constant factors and modifying the coefficient of the log.
<bramc> No blocks are indexed by position, pulling data from one is a single cache miss
<bsm1175321> It sounds to me like your locality argument is increasing the "effective size" of the cache. No?
<bramc> Uh, sort of. The root block gets pulled in first, then you go several bits deep without having to leave that block, then you get referred to another block, which is of course a cache miss, which leads you a few more bits deep, then refers to another block...
mrkent has quit []
rusty has joined #bitcoin-wizards
<bramc> There's a big difference between branch and leaf blocks, in that branch blocks are balanced and fixed position while leaf blocks do dynamic memory allocation using append to the end and sweep once they hit the end
<bramc> of the block
NewLiberty has joined #bitcoin-wizards
<bsm1175321> So I'd argue that there's a range of set sizes where these optimizations are important. e.g. with 16 caches of 16kb it smooths out the log curve of a < 16kb set to one of 256kb which is entirely in the L2 cache. Likewise a smoother transition from L2 to L3. So what is your use case, and do you expect the set size to be in a range where these optimizations will make a big difference?
<bramc> This is for the utxo set, which I think is about 200 million entries, although maybe I just made that number up
<bsm1175321> So much larger than the largest cache around.
<bsm1175321> And growing :-
<bsm1175321> :-(
<bramc> Yes vastly larger.
tjader has quit [Ping timeout: 276 seconds]
<bsm1175321> Are you sure these optimizations are noticeable on a set size very much larger than the cache?
<bramc> The TODOs at the top of this file are terrifying. Starting with porting to C.
<bsm1175321> heheee
<bramc> They matter more the larger the set size is
<bsm1175321> I think you're changing the coefficient of the log A*log(n)
<bramc> The trick is to make the block size reasonable. I have that as a parameter, it goes up by (roughly) factors of 2.
<bramc> If the block size is too big it gets cache misses within block, if it's too small there are cache misses elsewhere.
<bsm1175321> Ok I have no doubt these kinds of optimizations could change A by a factor 2 or more.
<bramc> My computer's about to die, have to leave the coffee shop and head home, be back in a bit.
<bramc> I'm guessing my implementation will be about a factor of 4 better than a simple one. It could easily be anywhere in the range 2-20 though.
Ylbam has quit [Quit: Connection closed for inactivity]
bramc has quit [Quit: This computer has gone to sleep]
jtimon has quit [Ping timeout: 250 seconds]
tjader has joined #bitcoin-wizards
mihar has quit [Ping timeout: 276 seconds]
dEBRUYNE_ has quit [Quit: Leaving]
NewLiberty has quit [Ping timeout: 240 seconds]
<bsm1175321> ;;tell bramc Wait I see. In a block of blocks, that can be entirely loaded into the cache, you can search for the next sub-block. And a sub-block fits within the cache. So in principle the search could be composed from (# cache loads)*(log(cache size)) + (# cache loads)*(cache load time)
<gribble> Error: I haven't seen bramc, I'll let you do the telling.
<bsm1175321> wtf
adam3us has joined #bitcoin-wizards
bramc has joined #bitcoin-wizards
brg444 has joined #bitcoin-wizards
zmachine has quit [Ping timeout: 265 seconds]
BananaLotus has joined #bitcoin-wizards
<bramc> bsm117532 I think that's right although my brain is jello at the moment
guruvan has joined #bitcoin-wizards
<bsm1175321> Which is A*log(# caches)*log(n) + const
<bsm1175321> Well, cool, nonetheless, to give L1 cache speed to a much larger data structure. :-)
TheSeven has quit [Ping timeout: 245 seconds]
<bsm1175321> Have a good night. I'll make you do O(n) analysis on graph algorithms when you least expect it! ;-)
zmachine has joined #bitcoin-wizards
GGuyZ has quit [Quit: GGuyZ]
TheSeven has joined #bitcoin-wizards
GGuyZ has joined #bitcoin-wizards
adam3us has quit [Quit: Leaving.]
rusty has quit [Ping timeout: 272 seconds]
oneeman has quit [Quit: Leaving]
sparetire has quit [Quit: sparetire]
danielsocials has joined #bitcoin-wizards
NewLiberty has joined #bitcoin-wizards
brg444 has quit [Ping timeout: 252 seconds]
ttttemp has quit [Remote host closed the connection]
danielsocials has quit [Remote host closed the connection]
ttttemp has joined #bitcoin-wizards
belcher has quit [Quit: Leaving]
memymo has joined #bitcoin-wizards
voxelot has quit [Ping timeout: 265 seconds]
voxelot has joined #bitcoin-wizards
priidu has quit [Ping timeout: 276 seconds]
justanotheruser has quit [Read error: Connection reset by peer]
justanotheruser has joined #bitcoin-wizards
tjader has quit [Ping timeout: 276 seconds]
tjader has joined #bitcoin-wizards
RoboTedd_ has quit [Remote host closed the connection]
RoboTeddy has joined #bitcoin-wizards
NewLiberty has quit [Ping timeout: 260 seconds]
p15 has joined #bitcoin-wizards
ttttemp_ has joined #bitcoin-wizards
kang_ has left #bitcoin-wizards [#bitcoin-wizards]
adam3us has joined #bitcoin-wizards
voxelot has quit [Ping timeout: 250 seconds]
mpmcsweeney has joined #bitcoin-wizards
voxelot has joined #bitcoin-wizards
GreenIsMyPepper has quit [Ping timeout: 250 seconds]
GreenIsMyPepper has joined #bitcoin-wizards
<Luke-Jr> random idea: would it cost much for blocks to commit to the heights of each tx input? this would be to make it possible to fraud-proof that inputs don't exist
<Luke-Jr> (maybe possible to bundle into segwit?)
voxelot has quit [Ping timeout: 260 seconds]
dcousens has joined #bitcoin-wizards
zzyzx has quit [Quit: ChatZilla 0.9.92 [SeaMonkey 2.39/20151103191810]]
bit2017 has joined #bitcoin-wizards
nivah has quit [Ping timeout: 264 seconds]
voxelot has joined #bitcoin-wizards
adam3us has quit [Quit: Leaving.]
T23WS has joined #bitcoin-wizards
GGuyZ has quit [Quit: GGuyZ]
T23WS has quit [Client Quit]
DougieBot5000 has joined #bitcoin-wizards
nonaTure has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
voxelot has quit [Ping timeout: 260 seconds]
Ylbam has joined #bitcoin-wizards
priidu has joined #bitcoin-wizards
memymo has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
murch has joined #bitcoin-wizards
Alopex has quit [Remote host closed the connection]
Alopex has joined #bitcoin-wizards
tjader has quit [Ping timeout: 276 seconds]
tjader has joined #bitcoin-wizards
GAit has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
nonaTure has quit [Quit: Leaving.]
phiche has joined #bitcoin-wizards
ozanyurt has joined #bitcoin-wizards
Erik_dc has joined #bitcoin-wizards
phiche has quit [Ping timeout: 256 seconds]
phiche has joined #bitcoin-wizards
erasmospunk has joined #bitcoin-wizards
bramc has quit [Quit: This computer has gone to sleep]
andy-logbot has quit [Remote host closed the connection]
andy-logbot has joined #bitcoin-wizards
* andy-logbot is logging
AaronvanW has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 250 seconds]
Guyver2 has quit [Ping timeout: 245 seconds]
Erik_dc has quit [Remote host closed the connection]
dcousens has quit [Ping timeout: 265 seconds]
wumpus has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
ozanyurt has quit [Read error: Connection reset by peer]
ozanyurt has joined #bitcoin-wizards
dnaleor has joined #bitcoin-wizards
bit2017 has quit [Ping timeout: 240 seconds]
ttttemp has quit [Remote host closed the connection]
rusty has joined #bitcoin-wizards
roconnor has quit [Ping timeout: 272 seconds]
dcousens has joined #bitcoin-wizards
bit2017 has joined #bitcoin-wizards
priidu has quit [Ping timeout: 250 seconds]
stevenroose_ has joined #bitcoin-wizards
phiche has quit [Read error: Connection reset by peer]
phiche has joined #bitcoin-wizards
Linus_ has joined #bitcoin-wizards
bit2017 has quit [Ping timeout: 240 seconds]
bit2017 has joined #bitcoin-wizards
Erik_dc has joined #bitcoin-wizards
rusty has quit [Ping timeout: 240 seconds]
erasmospunk has quit [Remote host closed the connection]
veleiro has quit [Ping timeout: 265 seconds]
Xzibit17 has quit [Quit: Connection closed for inactivity]
tjader has quit [Ping timeout: 276 seconds]
tjader has joined #bitcoin-wizards
bit2017 has quit [Read error: Connection reset by peer]
bit2017 has joined #bitcoin-wizards
Emcy has joined #bitcoin-wizards
Emcy has quit [Changing host]
Emcy has joined #bitcoin-wizards
Erik_dc has quit [Remote host closed the connection]
dEBRUYNE has joined #bitcoin-wizards
kang_ has joined #bitcoin-wizards
<kang_> cuckoo : a memory-bound graph-theoretic proof-of-work system https://github.com/tromp/cuckoo
<fluffypony> kang_: been discussed here many times, tromp_ is a regular a participant in this channel
<kang_> I realized
<kang_> Sorry. Is it really trivial to verify?
<kang_> How can a solution to TSP be trivial to verify?
<fluffypony> it's outside my wheelhouse, but I'm sure when he's around tromp_ will comment
erasmospunk has joined #bitcoin-wizards
kang_ has quit [Quit: Page closed]
tjader has quit [Ping timeout: 276 seconds]
roman___ has joined #bitcoin-wizards
tjader has joined #bitcoin-wizards
trippysalmon has joined #bitcoin-wizards
nivah has joined #bitcoin-wizards
bit2017 has quit [Ping timeout: 250 seconds]
ThomasV has quit [Ping timeout: 260 seconds]
jtimon has joined #bitcoin-wizards
GAit has joined #bitcoin-wizards
rubensayshi has quit [Ping timeout: 265 seconds]
zzyzx has joined #bitcoin-wizards
erasmospunk has quit [Remote host closed the connection]
nonaTure has joined #bitcoin-wizards
ThomasV has joined #bitcoin-wizards
dEBRUYNE has quit [Ping timeout: 265 seconds]
GGuyZ has joined #bitcoin-wizards
bityogi has joined #bitcoin-wizards
p15 has quit [Ping timeout: 240 seconds]
GAit has quit [Quit: Leaving.]
GAit has joined #bitcoin-wizards
GGuyZ has quit [Quit: GGuyZ]
GGuyZ has joined #bitcoin-wizards
tjader has quit [Ping timeout: 276 seconds]
sparetire has joined #bitcoin-wizards
null_radix has quit [K-Lined]
Pugg has quit [K-Lined]
aem has quit [K-Lined]
nivah has quit [Ping timeout: 250 seconds]
tjader has joined #bitcoin-wizards
murch has quit [Remote host closed the connection]
adam3us has joined #bitcoin-wizards
binaryFate has joined #bitcoin-wizards
erasmospunk has joined #bitcoin-wizards
GGuyZ has quit [Ping timeout: 250 seconds]
aem has joined #bitcoin-wizards
Pugg has joined #bitcoin-wizards
dEBRUYNE has joined #bitcoin-wizards
Yoghur114 has joined #bitcoin-wizards
null_radix has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
GAit has joined #bitcoin-wizards
GGuyZ has joined #bitcoin-wizards
binaryFate_ has joined #bitcoin-wizards
aem is now known as aem
binaryFate has quit [Quit: Konversation terminated!]
NewLiberty has joined #bitcoin-wizards
AaronvanW is now known as NewName
NewName is now known as AaronvanW
priidu has joined #bitcoin-wizards
binaryFate_ has quit [Quit: ZNC ftw]
binaryFate has joined #bitcoin-wizards
NewLiberty has quit [Ping timeout: 250 seconds]
NewLiberty has joined #bitcoin-wizards
binaryFate has quit [Quit: ZNC ftw]
binaryFate has joined #bitcoin-wizards
bit2017 has joined #bitcoin-wizards
binaryFate has quit [Quit: ZNC ftw]
binaryFate has joined #bitcoin-wizards
binaryFate has quit [Client Quit]
binaryFate has joined #bitcoin-wizards
tjader has quit [Ping timeout: 276 seconds]
belcher has joined #bitcoin-wizards
binaryFate has quit [Client Quit]
binaryFate has joined #bitcoin-wizards
tjader has joined #bitcoin-wizards
GAit has quit [Read error: Connection reset by peer]
binaryFate has quit [Client Quit]
GAit has joined #bitcoin-wizards
GAit has quit [Excess Flood]
binaryFate has joined #bitcoin-wizards
erasmospunk has quit [Remote host closed the connection]
GAit has joined #bitcoin-wizards
erasmospunk has joined #bitcoin-wizards
NewLiberty has quit [Ping timeout: 260 seconds]
wallet42 has joined #bitcoin-wizards
binaryFateCloud has quit [Remote host closed the connection]
erasmosp_ has joined #bitcoin-wizards
erasmospunk has quit [Ping timeout: 256 seconds]
Burrito has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 250 seconds]
<tromp__> it's not TSP; it's a cycle of 42 edges
blackwraith has joined #bitcoin-wizards
<tromp__> it's trivial to check whether 42 given edges form a cycle
memymo has joined #bitcoin-wizards
<tromp__> cuckoo cycle just appeared on Hacker News at https://news.ycombinator.com/item?id=10957765
priidu has quit [Ping timeout: 265 seconds]
dnaleor has quit [Remote host closed the connection]
ThomasV has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
Emcy_ has joined #bitcoin-wizards
binns has quit [Quit: Updating details, brb]
binns has joined #bitcoin-wizards
Emcy_ has quit [Remote host closed the connection]
nonaTure has quit [Ping timeout: 272 seconds]
GAit has quit [Quit: Leaving.]
nonaTure has joined #bitcoin-wizards
arowser_ has joined #bitcoin-wizards
arowser has quit [Read error: Connection reset by peer]
adam3us has quit [Quit: Leaving.]
GAit has joined #bitcoin-wizards
brg444 has joined #bitcoin-wizards
tjader has quit [Ping timeout: 276 seconds]
Yoghur114 has quit [Quit: Konversation terminated!]
trippysalmon has quit [Read error: Connection reset by peer]
Yoghur114 has joined #bitcoin-wizards
tjader has joined #bitcoin-wizards
gocrazy has quit [Ping timeout: 240 seconds]
<AdrianG> nice
memymo has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
Tasoshi has quit [Ping timeout: 276 seconds]
GAit has quit [Quit: Leaving.]
voxelot has joined #bitcoin-wizards
GAit has joined #bitcoin-wizards
<maaku> Luke-Jr: that was in sipa's original segwit presentation (backpointers, an idea due to rusty)
<maaku> it's not yet in the segwit branch
<maaku> tromp__: how mature is the cuckoo codebase?
dEBRUYNE has quit [Quit: Leaving]
merlincorey has quit [Changing host]
merlincorey has joined #bitcoin-wizards
Tasoshi has joined #bitcoin-wizards
voxelot has quit [Ping timeout: 260 seconds]
sCOGSBY has joined #bitcoin-wizards
voxelot has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
GAit has joined #bitcoin-wizards
murch has joined #bitcoin-wizards
Monthrect is now known as Piper-Off
NewLiberty has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 250 seconds]
sausage_factory has joined #bitcoin-wizards
blackwraith has quit [Ping timeout: 265 seconds]
GGuyZ has quit [Quit: GGuyZ]
<Luke-Jr> maaku: yet? :x
roconnor has joined #bitcoin-wizards
GGuyZ has joined #bitcoin-wizards
ThomasV has quit [Ping timeout: 250 seconds]
blackwraith has joined #bitcoin-wizards
tjader has quit [Ping timeout: 276 seconds]
adam3us has joined #bitcoin-wizards
sausage_factory has quit [Ping timeout: 240 seconds]
tjader has joined #bitcoin-wizards
oneeman has joined #bitcoin-wizards
murch has quit [Remote host closed the connection]
zookolaptop has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
dEBRUYNE has joined #bitcoin-wizards
Guyver2 has joined #bitcoin-wizards
Piper-Off is now known as Monthrect
dEBRUYNE has quit [Quit: Leaving]
<maaku> Luke-Jr: patches welcome
GAit has joined #bitcoin-wizards
<wallet42> maaku: what kind of backpointers?
<maaku> wallet42: a merkle tree of the block nth block, mth transaction where the output being spent originated
<maaku> it's actually quite trivial, probably a dozen lines of code
<maaku> the merkle sum tree of fees is only slightly more complicated
<maaku> Luke-Jr: is you patricia trie implementation in C hosted anywhere?
GAit has quit [Quit: Leaving.]
GAit has joined #bitcoin-wizards
<Luke-Jr> maaku: never got it finished still :<
b-itcoinssg has joined #bitcoin-wizards
<zookolaptop> maaku: what do you want a patricia trie for?
zookolaptop is now known as zooko
<zooko> maaku: I mean, I see it is for this backpointer index thingie.
<zooko> maaku: but I don't know -- is this something you'd need to deploy to others, integrate into bitcoin-core or anything like that?
memymo has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
NewLiberty has quit [Ping timeout: 260 seconds]
<maaku> no it is not for that, unrelated request :)
<maaku> it is not consensus code (for bitcoin, anyway)
<zooko> How important is concrete performance?
<zooko> I've had great success using Judy Trees for some computational linguistics hacking with my then-wife.
<zooko> Performed beautifully.
<tromp__> maaku: somewhat mature in terms of performance. but written in my overly concise and underdocumented style.
<gmaxwell> zooko: just don't read the source code for libjudy.
mpmcsweeney has joined #bitcoin-wizards
mpmcsweeney has quit [Client Quit]
<zooko> gmaxwell: oh I know.
<zooko> gmaxwell: that's why I asked what the purpose of this was before recommending it. :-)
<maaku> zooko: it woud be for consensus code (merged mining, among other things) just not on bitcoin core
adlai has quit [Ping timeout: 250 seconds]
<maaku> so clean and concise is preferred :)
<zooko> maaku: ooh, ok.
<zooko> Then I do not recommend libjudy.
voxelot has quit [Ping timeout: 240 seconds]
<zooko> I wonder what *is* the cleanest, simplest implementation of some kind of nice tree structure for such a purpose…
stevenroose_ has quit [Ping timeout: 245 seconds]
tjader has quit [Ping timeout: 276 seconds]
GGuyZ_ has joined #bitcoin-wizards
GGuyZ has quit [Read error: Connection reset by peer]
GGuyZ_ is now known as GGuyZ
dEBRUYNE has joined #bitcoin-wizards
tjader has joined #bitcoin-wizards
raedah has quit [Quit: Leaving]
ratbanebo has joined #bitcoin-wizards
phiche has quit [Quit: Leaving.]
NewLiberty has joined #bitcoin-wizards
kefkius has joined #bitcoin-wizards
voxelot has joined #bitcoin-wizards
Cory has quit [Ping timeout: 276 seconds]
ozanyurt_ has joined #bitcoin-wizards
GAit has joined #bitcoin-wizards
ozanyurt has quit [Ping timeout: 250 seconds]
justanotheruser has quit [Ping timeout: 250 seconds]
Cory has joined #bitcoin-wizards
adlie is now known as adlai
justanotheruser has joined #bitcoin-wizards
adlie has joined #bitcoin-wizards
<tromp__> btw, earlier versions of my Go counting code used judy arrays
<tromp__> back when the data sets all fit in main memory
phiche has joined #bitcoin-wizards
bramc has joined #bitcoin-wizards
bramc is now known as Guest76435
ozanyurt has joined #bitcoin-wizards
justanotheruser has quit [Ping timeout: 250 seconds]
ozanyurt_ has quit [Read error: Connection reset by peer]
justanotheruser has joined #bitcoin-wizards
<maaku> zooko yeah I'm assuming we'll have to roll our own
<maaku> I didn't find anything in my previous search
<zooko> What programming language?
<Guest76435> I'm currently working on a patricia trie https://github.com/bramcohen/MerkleSet
GGuyZ has quit [Quit: GGuyZ]
Guest76435 is now known as bramc
NewLiberty has quit [Ping timeout: 240 seconds]
<bramc> Not sure what a judy tee is
<gmaxwell> a radix-256 trie with an implementation that is something like 30k lines of highly macrofied C code. :) Pretty fast though.
<zooko> gmaxwell: it's not *just* a radix-256 trie, either... It switches among representations at each node based on the density of that node's population ...
wallet42 has quit [Quit: Leaving.]
adam3us has quit [Quit: Leaving.]
ThomasV has joined #bitcoin-wizards
GAit has quit [Quit: Leaving.]
paveljanik has quit [Quit: Leaving]
GAit has joined #bitcoin-wizards
GAit has quit [Client Quit]
GAit has joined #bitcoin-wizards
<bramc> This sounds similar to what I'm doing, but I'm being much cruder and simpler about it
phiche has quit [Ping timeout: 276 seconds]
phiche has joined #bitcoin-wizards
<bramc> What I'm doing is a patricia trie, and has different representations but there are only two: branch and leaf
<zooko> *nod*
GAit has quit [Client Quit]
tjader has quit [Ping timeout: 276 seconds]
b-itcoinssg has quit [Quit: Connection closed for inactivity]
erasmosp_ has quit [Remote host closed the connection]
tjader has joined #bitcoin-wizards
erasmospunk has joined #bitcoin-wizards
dEBRUYNE has quit [Ping timeout: 250 seconds]
GAit has joined #bitcoin-wizards
GAit has quit [Client Quit]
erasmospunk has quit [Ping timeout: 260 seconds]
Cory has quit [Ping timeout: 250 seconds]
ratbanebo has quit [Remote host closed the connection]
ratbanebo has joined #bitcoin-wizards
GGuyZ has joined #bitcoin-wizards
Cory has joined #bitcoin-wizards
GAit has joined #bitcoin-wizards
ratbanebo has quit [Ping timeout: 250 seconds]
dEBRUYNE has joined #bitcoin-wizards
voxelot has quit [Ping timeout: 240 seconds]
ozanyurt has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
adam3us has joined #bitcoin-wizards
adam3us1 has joined #bitcoin-wizards
<bramc> zooko, Note that that file isn't done being written yet, much less debugged, but the comment at the top explaining the data format is fairly comprehensive, if a bit ad-hoc in its notation.
<zooko> *nod*
phiche1 has joined #bitcoin-wizards
phiche has quit [Ping timeout: 240 seconds]
adam3us has quit [Ping timeout: 250 seconds]
voxelot has joined #bitcoin-wizards
adam3us1 has quit [Ping timeout: 260 seconds]
GGuyZ has quit [Quit: GGuyZ]
Keefe_ is now known as Keefe
erasmospunk has joined #bitcoin-wizards
justanotheruser has quit [Read error: Connection reset by peer]
voxelot has quit [Ping timeout: 240 seconds]
justanotheruser has joined #bitcoin-wizards
ratbanebo has joined #bitcoin-wizards
phiche1 has quit [Quit: Leaving.]
ThomasV has quit [Ping timeout: 250 seconds]
ratbanebo has quit [Ping timeout: 245 seconds]
voxelot has joined #bitcoin-wizards
rusty has joined #bitcoin-wizards
rusty has quit [Client Quit]
Guyver2 has quit [Read error: Connection reset by peer]
dEBRUYNE has quit [Ping timeout: 265 seconds]
wallet421 has joined #bitcoin-wizards
wallet421 has joined #bitcoin-wizards
wallet42 has quit [Client Quit]
ozanyurt has joined #bitcoin-wizards
NewLiberty has joined #bitcoin-wizards
brg444 has quit [Quit: Page closed]
NewLiberty has quit [Read error: Connection reset by peer]
NewLiberty has joined #bitcoin-wizards
tjader has quit [Ping timeout: 276 seconds]
dEBRUYNE has joined #bitcoin-wizards
ozanyurt has quit [Read error: Connection reset by peer]
ozanyurt has joined #bitcoin-wizards
tjader has joined #bitcoin-wizards
MrHodl has quit [Read error: Connection reset by peer]
coinoperated has quit [Ping timeout: 265 seconds]
Linus_ has quit [Ping timeout: 276 seconds]
GAit has quit [Quit: Leaving.]
voxelot has quit [Ping timeout: 250 seconds]
ratbanebo has joined #bitcoin-wizards
mkarrer has quit []
ratbanebo has quit [Ping timeout: 264 seconds]
mkarrer has joined #bitcoin-wizards
voxelot has joined #bitcoin-wizards
justanotheruser has quit [Read error: Connection reset by peer]
justanotheruser has joined #bitcoin-wizards
GAit has joined #bitcoin-wizards
wallet42 has joined #bitcoin-wizards
GAit has quit [Read error: Connection reset by peer]
GAit has joined #bitcoin-wizards
memymo has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
PaulCapestany has quit [Quit: .]
AaronvanW has joined #bitcoin-wizards
PaulCapestany has joined #bitcoin-wizards