#bitcoin-wizards on 2016-01-23 — irc logs at freenode.irclog.whitequark.org

2015-10-30 00:53 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

00:00 tjader has quit [Ping timeout: 276 seconds]

00:04 tjader has joined #bitcoin-wizards

00:05 ThomasV has quit [Ping timeout: 256 seconds]

00:07 nonaTure has quit [Quit: Leaving.]

00:14 Jeremy_Rand_2 has joined #bitcoin-wizards

00:18 dnaleor has joined #bitcoin-wizards

00:18 GGuyZ has quit [Read error: Connection reset by peer]

00:18 AndChat|435584 has joined #bitcoin-wizards

00:18 GGuyZ has joined #bitcoin-wizards

00:19 MrChrisJ_ has joined #bitcoin-wizards

00:20 skyraider_ has quit [Quit: Connection closed for inactivity]

00:20 MrChrisJ_ has quit [Client Quit]

00:21 MrChrisJ has quit [Ping timeout: 256 seconds]

00:23 GAit has quit [Quit: Leaving.]

00:28 RoboTedd_ has joined #bitcoin-wizards

00:31 RoboTeddy has quit [Ping timeout: 265 seconds]

00:32 memymo has joined #bitcoin-wizards

00:35 mkarrer_ has quit [Remote host closed the connection]

00:36 GAit has joined #bitcoin-wizards

00:38 dcousens has quit [Ping timeout: 264 seconds]

00:43 chjj has quit [Quit: null]

00:43 chjj has joined #bitcoin-wizards

00:45 chjj has quit [Client Quit]

00:45 tjader has quit [Ping timeout: 276 seconds]

00:47 chjj has joined #bitcoin-wizards

00:50 tjader has joined #bitcoin-wizards

00:58 markus-k_ has joined #bitcoin-wizards

00:58 mrkent has joined #bitcoin-wizards

01:00 markus-k_ has quit [Max SendQ exceeded]

01:03 voxelot has quit [Ping timeout: 240 seconds]

01:07 TheSeven has quit [Ping timeout: 240 seconds]

01:09 GGuyZ has quit [Quit: GGuyZ]

01:13 polyclef has quit [Ping timeout: 265 seconds]

01:14 roman has quit [Remote host closed the connection]

01:16 TheSeven has joined #bitcoin-wizards

01:16 bobke has joined #bitcoin-wizards

01:17 brg444 has quit [Quit: Page closed]

01:18 kang_ has joined #bitcoin-wizards

01:22 BananaLotus has quit [Remote host closed the connection]

01:22 guruvan has quit [Remote host closed the connection]

01:22 kefkius has quit [Remote host closed the connection]

01:24 arowser has quit [Quit: No Ping reply in 180 seconds.]

01:24 arowser has joined #bitcoin-wizards

01:25 Giszmo has quit [Ping timeout: 272 seconds]

01:29 alpalp has quit [Remote host closed the connection]

01:34 AaronvanW has quit [Read error: Connection reset by peer]

01:35 AaronvanW has joined #bitcoin-wizards

01:37 danielsocials has joined #bitcoin-wizards

01:38 danielsocials has quit [Remote host closed the connection]

01:41 memymo has quit [Quit: My Mac has gone to sleep. ZZZzzz…]

01:41 GGuyZ has joined #bitcoin-wizards

01:42 alpalp has joined #bitcoin-wizards

01:45 GAit has quit [Quit: Leaving.]

01:46 adam3us has joined #bitcoin-wizards

01:46 adam3us has quit [Client Quit]

01:46 adam3us has joined #bitcoin-wizards

01:51 funkenstein_ has joined #bitcoin-wizards

01:51 oneeman has joined #bitcoin-wizards

02:03 dnaleor has quit [Quit: Leaving]

02:04 GGuyZ has quit [Quit: GGuyZ]

02:08 kyletorpey has joined #bitcoin-wizards

02:08 Giszmo has joined #bitcoin-wizards

02:09 dnaleor has joined #bitcoin-wizards

02:12 Giszmo has quit [Ping timeout: 240 seconds]

02:13 kyletorpey has left #bitcoin-wizards [#bitcoin-wizards]

02:15 tjader has quit [Ping timeout: 276 seconds]

02:18 moa has quit [Quit: Leaving.]

02:20 tjader has joined #bitcoin-wizards

02:24 roconnor has joined #bitcoin-wizards

02:27 <gmaxwell> tromp_: CONGRATS ON L19 computation!

02:30 binns has joined #bitcoin-wizards

02:30 binns is now known as Guest19968

02:33 Guest19968 has quit [Changing host]

02:33 Guest19968 has joined #bitcoin-wizards

02:33 Guest19968 is now known as binns

02:35 GGuyZ has joined #bitcoin-wizards

02:35 Giszmo has joined #bitcoin-wizards

02:35 binns is now known as wbinns

02:35 wbinns is now known as binns

02:39 go1111111 has quit [Ping timeout: 260 seconds]

02:48 binns has quit [Quit: Updating details, brb]

02:48 binns has joined #bitcoin-wizards

02:53 go1111111 has joined #bitcoin-wizards

02:54 <tromp_> thanks, Gregory!

02:54 AaronvanW has quit [Ping timeout: 250 seconds]

02:55 arowser has quit [Quit: No Ping reply in 180 seconds.]

02:55 danielsocials has joined #bitcoin-wizards

02:55 arowser has joined #bitcoin-wizards

02:58 bityogi has quit [Quit: My Mac has gone to sleep. ZZZzzz…]

02:59 <bsm1175321> Whazzat?

02:59 <tromp_> https://news.ycombinator.com/item?id=10950875

03:00 <bsm1175321> Darn. There goes my PoW algorithm...

03:00 <tromp_> perfect for a 9 month block interval:-)

03:01 <bsm1175321> Hey, if my landlord accepts yearly rent...

03:02 adam3us has quit [Quit: Leaving.]

03:03 <bsm1175321> I actually typed: isprime(2**74207281-1) into Maple today. Perhaps I was over-optimistic.

03:04 <bsm1175321> there must be special techniques for merseinne primes...

03:04 sCOGSBY has quit [Remote host closed the connection]

03:04 chjj_ has joined #bitcoin-wizards

03:09 gavink has quit [Ping timeout: 245 seconds]

03:11 <tromp_> i think it's called the lucas-lehmer test

03:11 chjj_ has quit [Quit: null]

03:11 bramc has joined #bitcoin-wizards

03:12 <bramc> Okay, so I'm partway into writing the insertion code now, and somewhat unrelatedly have run into a bit of a moral dilemma

03:14 dnaleor has quit [Quit: Leaving]

03:15 <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.

03:17 binns has quit [Quit: Updating details, brb]

03:17 <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?

03:17 binns has joined #bitcoin-wizards

03:17 <bsm1175321> You really want this fast, don't you?

03:18 <bsm1175321> log(n) vs O(1) is a good problem to have.

03:18 <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.

03:18 <bsm1175321> I'm wrestling with O(n^3) on some braid algorithms.

03:18 Guest75253 is now known as mr_burdell

03:18 o3u is now known as Fistful_of_Coins

03:18 mr_burdell has quit [Changing host]

03:18 mr_burdell has joined #bitcoin-wizards

03:18 <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.

03:19 funkenstein_ has left #bitcoin-wizards ["Leaving"]

03:19 <bramc> Technically log(log(n)) isn't a constant factor, but it acts a lot like it in practice.

03:19 <bsm1175321> Hashes should be O(1) no? You're probably using a more sophisticated analysis of the buckets than me...

03:20 <bramc> Yes hashes are O(1). It's my set which is O(log(log(n))

03:20 <bramc> )

03:20 <bsm1175321> Uh...How did you add another log?

03:21 <bramc> The location of nodes in memory is set up so that they're near each other.

03:21 <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.

03:21 voxelot has joined #bitcoin-wizards

03:22 <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

03:22 <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?

03:23 <bsm1175321> What is a "block" in this context?

03:23 <bramc> The fanout within a block is limited, it only goes so many levels deep before pointing to another block

03:24 danielsocials has quit [Remote host closed the connection]

03:24 <bsm1175321> I see, so the n of the block-based algorithm is log(n) for the blocks.

03:25 <bsm1175321> Wait, that can't work...

03:26 <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.

03:26 <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?

03:26 NewLiberty has quit [Ping timeout: 250 seconds]

03:27 <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.

03:27 <bsm1175321> I'm afraid you know a lot more about caches than me.

03:28 <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.

03:28 <bramc> Some concept as disk accesses, but smaller distances and smaller times.

03:29 <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.

03:30 <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?

03:30 <bsm1175321> *larger

03:30 Burrito has quit [Quit: Leaving]

03:30 <bsm1175321> Jumps due to the speed of the caches.

03:33 <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

03:33 <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.

03:34 <bramc> Mostly I have a giant byte array called self.memory

03:35 <bsm1175321> Shouldn't this just smooth out the transition between size(L1), size(L2), and size(L3) rather than make it log log?

03:36 <bsm1175321> I mean, the asymptotic limit, for a very large set, the cache doesn't help, no?

03:36 <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.

03:37 <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.

03:37 <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...

03:38 <bsm1175321> So the cache is adding constant factors and modifying the coefficient of the log.

03:38 <bramc> No blocks are indexed by position, pulling data from one is a single cache miss

03:39 <bsm1175321> It sounds to me like your locality argument is increasing the "effective size" of the cache. No?

03:41 <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...

03:41 mrkent has quit []

03:42 rusty has joined #bitcoin-wizards

03:43 <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

03:43 <bramc> of the block

03:43 NewLiberty has joined #bitcoin-wizards

03:43 <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?

03:44 <bramc> This is for the utxo set, which I think is about 200 million entries, although maybe I just made that number up

03:44 <bsm1175321> So much larger than the largest cache around.

03:45 <bsm1175321> And growing :-

03:45 <bsm1175321> :-(

03:45 <bramc> Yes vastly larger.

03:45 tjader has quit [Ping timeout: 276 seconds]

03:45 <bsm1175321> Are you sure these optimizations are noticeable on a set size very much larger than the cache?

03:45 <bramc> The TODOs at the top of this file are terrifying. Starting with porting to C.

03:45 <bsm1175321> heheee

03:46 <bramc> They matter more the larger the set size is

03:46 <bsm1175321> I think you're changing the coefficient of the log A*log(n)

03:46 <bramc> The trick is to make the block size reasonable. I have that as a parameter, it goes up by (roughly) factors of 2.

03:46 <bramc> If the block size is too big it gets cache misses within block, if it's too small there are cache misses elsewhere.

03:47 <bsm1175321> Ok I have no doubt these kinds of optimizations could change A by a factor 2 or more.

03:47 <bramc> My computer's about to die, have to leave the coffee shop and head home, be back in a bit.

03:48 <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.

03:48 Ylbam has quit [Quit: Connection closed for inactivity]

03:48 bramc has quit [Quit: This computer has gone to sleep]

03:50 jtimon has quit [Ping timeout: 250 seconds]

03:51 tjader has joined #bitcoin-wizards

03:55 mihar has quit [Ping timeout: 276 seconds]

03:57 dEBRUYNE_ has quit [Quit: Leaving]

03:57 NewLiberty has quit [Ping timeout: 240 seconds]

03:58 <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)

03:58 <gribble> Error: I haven't seen bramc, I'll let you do the telling.

03:58 <bsm1175321> wtf

04:00 adam3us has joined #bitcoin-wizards

04:02 bramc has joined #bitcoin-wizards

04:02 brg444 has joined #bitcoin-wizards

04:02 zmachine has quit [Ping timeout: 265 seconds]

04:02 BananaLotus has joined #bitcoin-wizards

04:03 <bramc> bsm117532 I think that's right although my brain is jello at the moment

04:03 guruvan has joined #bitcoin-wizards

04:06 <bsm1175321> Which is A*log(# caches)*log(n) + const

04:06 <bsm1175321> Well, cool, nonetheless, to give L1 cache speed to a much larger data structure. :-)

04:07 TheSeven has quit [Ping timeout: 245 seconds]

04:07 <bsm1175321> Have a good night. I'll make you do O(n) analysis on graph algorithms when you least expect it! ;-)

04:08 zmachine has joined #bitcoin-wizards

04:08 GGuyZ has quit [Quit: GGuyZ]

04:08 TheSeven has joined #bitcoin-wizards

04:12 GGuyZ has joined #bitcoin-wizards

04:15 adam3us has quit [Quit: Leaving.]

04:18 rusty has quit [Ping timeout: 272 seconds]

04:18 oneeman has quit [Quit: Leaving]

04:19 sparetire has quit [Quit: sparetire]

04:24 danielsocials has joined #bitcoin-wizards

04:25 NewLiberty has joined #bitcoin-wizards

04:41 brg444 has quit [Ping timeout: 252 seconds]

04:42 ttttemp has quit [Remote host closed the connection]

04:43 danielsocials has quit [Remote host closed the connection]

04:44 ttttemp has joined #bitcoin-wizards

04:45 belcher has quit [Quit: Leaving]

04:47 memymo has joined #bitcoin-wizards

04:52 voxelot has quit [Ping timeout: 265 seconds]

05:04 voxelot has joined #bitcoin-wizards

05:09 priidu has quit [Ping timeout: 276 seconds]

05:11 justanotheruser has quit [Read error: Connection reset by peer]

05:13 justanotheruser has joined #bitcoin-wizards

05:17 tjader has quit [Ping timeout: 276 seconds]

05:21 tjader has joined #bitcoin-wizards

05:33 RoboTedd_ has quit [Remote host closed the connection]

05:34 RoboTeddy has joined #bitcoin-wizards

05:39 NewLiberty has quit [Ping timeout: 260 seconds]

05:41 p15 has joined #bitcoin-wizards

05:42 ttttemp_ has joined #bitcoin-wizards

05:46 kang_ has left #bitcoin-wizards [#bitcoin-wizards]

05:54 adam3us has joined #bitcoin-wizards

05:58 voxelot has quit [Ping timeout: 250 seconds]

06:07 mpmcsweeney has joined #bitcoin-wizards

06:08 voxelot has joined #bitcoin-wizards

06:08 GreenIsMyPepper has quit [Ping timeout: 250 seconds]

06:10 GreenIsMyPepper has joined #bitcoin-wizards

06:34 <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

06:34 <Luke-Jr> (maybe possible to bundle into segwit?)

06:40 voxelot has quit [Ping timeout: 260 seconds]

06:41 dcousens has joined #bitcoin-wizards

06:46 zzyzx has quit [Quit: ChatZilla 0.9.92 [SeaMonkey 2.39/20151103191810]]

06:46 bit2017 has joined #bitcoin-wizards

06:48 nivah has quit [Ping timeout: 264 seconds]

06:52 voxelot has joined #bitcoin-wizards

06:55 adam3us has quit [Quit: Leaving.]

06:56 T23WS has joined #bitcoin-wizards

06:58 GGuyZ has quit [Quit: GGuyZ]

06:59 T23WS has quit [Client Quit]

07:33 DougieBot5000 has joined #bitcoin-wizards

07:44 nonaTure has joined #bitcoin-wizards

07:44 ThomasV has joined #bitcoin-wizards

07:54 voxelot has quit [Ping timeout: 260 seconds]

07:58 Ylbam has joined #bitcoin-wizards

08:00 priidu has joined #bitcoin-wizards

08:05 memymo has quit [Quit: My Mac has gone to sleep. ZZZzzz…]

08:13 murch has joined #bitcoin-wizards

08:15 Alopex has quit [Remote host closed the connection]

08:17 Alopex has joined #bitcoin-wizards

08:17 tjader has quit [Ping timeout: 276 seconds]

08:22 tjader has joined #bitcoin-wizards

08:22 GAit has joined #bitcoin-wizards

08:30 GAit has quit [Quit: Leaving.]

08:31 nonaTure has quit [Quit: Leaving.]

08:34 phiche has joined #bitcoin-wizards

08:36 ozanyurt has joined #bitcoin-wizards

08:56 Erik_dc has joined #bitcoin-wizards

08:57 phiche has quit [Ping timeout: 256 seconds]

08:57 phiche has joined #bitcoin-wizards

08:59 erasmospunk has joined #bitcoin-wizards

09:04 bramc has quit [Quit: This computer has gone to sleep]

09:05 andy-logbot has quit [Remote host closed the connection]

09:05 andy-logbot has joined #bitcoin-wizards

09:05 * andy-logbot is logging

09:05 AaronvanW has joined #bitcoin-wizards

09:07 Guyver2 has joined #bitcoin-wizards

09:20 ThomasV has quit [Ping timeout: 250 seconds]

09:20 Guyver2 has quit [Ping timeout: 245 seconds]

09:23 Erik_dc has quit [Remote host closed the connection]

09:28 dcousens has quit [Ping timeout: 265 seconds]

09:35 wumpus has joined #bitcoin-wizards

09:36 ThomasV has joined #bitcoin-wizards

09:40 ozanyurt has quit [Read error: Connection reset by peer]

09:41 ozanyurt has joined #bitcoin-wizards

09:44 dnaleor has joined #bitcoin-wizards

09:55 bit2017 has quit [Ping timeout: 240 seconds]

09:56 ttttemp has quit [Remote host closed the connection]

09:56 rusty has joined #bitcoin-wizards

10:04 roconnor has quit [Ping timeout: 272 seconds]

10:16 dcousens has joined #bitcoin-wizards

10:23 bit2017 has joined #bitcoin-wizards

10:25 priidu has quit [Ping timeout: 250 seconds]

10:28 stevenroose_ has joined #bitcoin-wizards

10:30 phiche has quit [Read error: Connection reset by peer]

10:31 phiche has joined #bitcoin-wizards

10:44 Linus_ has joined #bitcoin-wizards

10:48 bit2017 has quit [Ping timeout: 240 seconds]

10:51 bit2017 has joined #bitcoin-wizards

10:57 Erik_dc has joined #bitcoin-wizards

11:04 rusty has quit [Ping timeout: 240 seconds]

11:05 erasmospunk has quit [Remote host closed the connection]

11:10 veleiro has quit [Ping timeout: 265 seconds]

11:13 Xzibit17 has quit [Quit: Connection closed for inactivity]

11:17 tjader has quit [Ping timeout: 276 seconds]

11:22 tjader has joined #bitcoin-wizards

11:35 bit2017 has quit [Read error: Connection reset by peer]

11:35 bit2017 has joined #bitcoin-wizards

11:42 Emcy has joined #bitcoin-wizards

11:42 Emcy has quit [Changing host]

11:42 Emcy has joined #bitcoin-wizards

11:47 Erik_dc has quit [Remote host closed the connection]

11:57 dEBRUYNE has joined #bitcoin-wizards

12:01 kang_ has joined #bitcoin-wizards

12:02 <kang_> cuckoo : a memory-bound graph-theoretic proof-of-work system https://github.com/tromp/cuckoo

12:25 <fluffypony> kang_: been discussed here many times, tromp_ is a regular a participant in this channel

12:25 <kang_> I realized

12:26 <kang_> Sorry. Is it really trivial to verify?

12:26 <kang_> How can a solution to TSP be trivial to verify?

12:27 <fluffypony> it's outside my wheelhouse, but I'm sure when he's around tromp_ will comment

12:31 erasmospunk has joined #bitcoin-wizards

12:42 kang_ has quit [Quit: Page closed]

12:47 tjader has quit [Ping timeout: 276 seconds]

12:50 roman___ has joined #bitcoin-wizards

12:52 tjader has joined #bitcoin-wizards

12:52 trippysalmon has joined #bitcoin-wizards

12:59 nivah has joined #bitcoin-wizards

13:01 bit2017 has quit [Ping timeout: 250 seconds]

13:07 ThomasV has quit [Ping timeout: 260 seconds]

13:17 jtimon has joined #bitcoin-wizards

13:21 GAit has joined #bitcoin-wizards

13:26 rubensayshi has quit [Ping timeout: 265 seconds]

13:28 zzyzx has joined #bitcoin-wizards

13:30 erasmospunk has quit [Remote host closed the connection]

13:34 nonaTure has joined #bitcoin-wizards

13:34 ThomasV has joined #bitcoin-wizards

13:34 dEBRUYNE has quit [Ping timeout: 265 seconds]

13:53 GGuyZ has joined #bitcoin-wizards

13:53 bityogi has joined #bitcoin-wizards

13:59 p15 has quit [Ping timeout: 240 seconds]

14:01 GAit has quit [Quit: Leaving.]

14:11 GAit has joined #bitcoin-wizards

14:14 GGuyZ has quit [Quit: GGuyZ]

14:16 GGuyZ has joined #bitcoin-wizards

14:17 tjader has quit [Ping timeout: 276 seconds]

14:19 sparetire has joined #bitcoin-wizards

14:20 null_radix has quit [K-Lined]

14:20 Pugg has quit [K-Lined]

14:20 aem has quit [K-Lined]

14:21 nivah has quit [Ping timeout: 250 seconds]

14:22 tjader has joined #bitcoin-wizards

14:23 murch has quit [Remote host closed the connection]

14:23 adam3us has joined #bitcoin-wizards

14:25 binaryFate has joined #bitcoin-wizards

14:26 erasmospunk has joined #bitcoin-wizards

14:26 GGuyZ has quit [Ping timeout: 250 seconds]

14:40 aem has joined #bitcoin-wizards

14:40 Pugg has joined #bitcoin-wizards

14:41 dEBRUYNE has joined #bitcoin-wizards

14:42 Yoghur114 has joined #bitcoin-wizards

14:43 null_radix has joined #bitcoin-wizards

14:44 GAit has quit [Quit: Leaving.]

14:44 GAit has joined #bitcoin-wizards

14:46 GGuyZ has joined #bitcoin-wizards

14:57 binaryFate_ has joined #bitcoin-wizards

15:03 aem is now known as aem

15:09 binaryFate has quit [Quit: Konversation terminated!]

15:09 NewLiberty has joined #bitcoin-wizards

15:15 AaronvanW is now known as NewName

15:15 NewName is now known as AaronvanW

15:19 priidu has joined #bitcoin-wizards

15:32 binaryFate_ has quit [Quit: ZNC ftw]

15:32 binaryFate has joined #bitcoin-wizards

15:33 NewLiberty has quit [Ping timeout: 250 seconds]

15:36 NewLiberty has joined #bitcoin-wizards

15:38 binaryFate has quit [Quit: ZNC ftw]

15:38 binaryFate has joined #bitcoin-wizards

15:45 bit2017 has joined #bitcoin-wizards

15:45 binaryFate has quit [Quit: ZNC ftw]

15:46 binaryFate has joined #bitcoin-wizards

15:46 binaryFate has quit [Client Quit]

15:47 binaryFate has joined #bitcoin-wizards

15:47 tjader has quit [Ping timeout: 276 seconds]

15:49 belcher has joined #bitcoin-wizards

15:49 binaryFate has quit [Client Quit]

15:49 binaryFate has joined #bitcoin-wizards

15:52 tjader has joined #bitcoin-wizards

15:54 GAit has quit [Read error: Connection reset by peer]

15:54 binaryFate has quit [Client Quit]

15:54 GAit has joined #bitcoin-wizards

15:54 GAit has quit [Excess Flood]

15:54 binaryFate has joined #bitcoin-wizards

15:54 erasmospunk has quit [Remote host closed the connection]

15:55 GAit has joined #bitcoin-wizards

16:05 erasmospunk has joined #bitcoin-wizards

16:07 NewLiberty has quit [Ping timeout: 260 seconds]

16:09 wallet42 has joined #bitcoin-wizards

16:10 binaryFateCloud has quit [Remote host closed the connection]

16:11 erasmosp_ has joined #bitcoin-wizards

16:13 erasmospunk has quit [Ping timeout: 256 seconds]

16:17 Burrito has joined #bitcoin-wizards

16:22 ThomasV has quit [Ping timeout: 250 seconds]

16:24 <tromp__> it's not TSP; it's a cycle of 42 edges

16:24 blackwraith has joined #bitcoin-wizards

16:25 <tromp__> it's trivial to check whether 42 given edges form a cycle

16:26 memymo has joined #bitcoin-wizards

16:26 <tromp__> cuckoo cycle just appeared on Hacker News at https://news.ycombinator.com/item?id=10957765

16:27 priidu has quit [Ping timeout: 265 seconds]

16:32 dnaleor has quit [Remote host closed the connection]

16:34 ThomasV has joined #bitcoin-wizards

16:44 Emcy_ has joined #bitcoin-wizards

16:44 binns has quit [Quit: Updating details, brb]

16:45 binns has joined #bitcoin-wizards

16:45 Emcy_ has quit [Remote host closed the connection]

16:47 nonaTure has quit [Ping timeout: 272 seconds]

16:47 GAit has quit [Quit: Leaving.]

17:00 nonaTure has joined #bitcoin-wizards

17:06 arowser_ has joined #bitcoin-wizards

17:06 arowser has quit [Read error: Connection reset by peer]

17:14 adam3us has quit [Quit: Leaving.]

17:15 GAit has joined #bitcoin-wizards

17:17 brg444 has joined #bitcoin-wizards

17:17 tjader has quit [Ping timeout: 276 seconds]

17:21 Yoghur114 has quit [Quit: Konversation terminated!]

17:21 trippysalmon has quit [Read error: Connection reset by peer]

17:21 Yoghur114 has joined #bitcoin-wizards

17:22 tjader has joined #bitcoin-wizards

17:22 gocrazy has quit [Ping timeout: 240 seconds]

17:26 <AdrianG> nice

17:34 memymo has quit [Quit: My Mac has gone to sleep. ZZZzzz…]

17:39 Tasoshi has quit [Ping timeout: 276 seconds]

17:45 GAit has quit [Quit: Leaving.]

17:46 voxelot has joined #bitcoin-wizards

17:58 GAit has joined #bitcoin-wizards

17:58 <maaku> Luke-Jr: that was in sipa's original segwit presentation (backpointers, an idea due to rusty)

17:59 <maaku> it's not yet in the segwit branch

18:00 <maaku> tromp__: how mature is the cuckoo codebase?

18:01 dEBRUYNE has quit [Quit: Leaving]

18:03 merlincorey has quit [Changing host]

18:03 merlincorey has joined #bitcoin-wizards

18:04 Tasoshi has joined #bitcoin-wizards

18:06 voxelot has quit [Ping timeout: 260 seconds]

18:14 sCOGSBY has joined #bitcoin-wizards

18:18 voxelot has joined #bitcoin-wizards

18:21 GAit has quit [Quit: Leaving.]

18:24 GAit has joined #bitcoin-wizards

18:26 murch has joined #bitcoin-wizards

18:26 Monthrect is now known as Piper-Off

18:29 NewLiberty has joined #bitcoin-wizards

18:30 AaronvanW has quit [Ping timeout: 250 seconds]

18:32 sausage_factory has joined #bitcoin-wizards

18:34 blackwraith has quit [Ping timeout: 265 seconds]

18:37 GGuyZ has quit [Quit: GGuyZ]

18:40 <Luke-Jr> maaku: yet? :x

18:41 roconnor has joined #bitcoin-wizards

18:41 GGuyZ has joined #bitcoin-wizards

18:42 ThomasV has quit [Ping timeout: 250 seconds]

18:47 blackwraith has joined #bitcoin-wizards

18:48 tjader has quit [Ping timeout: 276 seconds]

18:49 adam3us has joined #bitcoin-wizards

18:49 sausage_factory has quit [Ping timeout: 240 seconds]

18:52 tjader has joined #bitcoin-wizards

19:02 oneeman has joined #bitcoin-wizards

19:05 murch has quit [Remote host closed the connection]

19:05 zookolaptop has joined #bitcoin-wizards

19:11 GAit has quit [Quit: Leaving.]

19:11 dEBRUYNE has joined #bitcoin-wizards

19:14 Guyver2 has joined #bitcoin-wizards

19:15 Piper-Off is now known as Monthrect

19:25 dEBRUYNE has quit [Quit: Leaving]

19:26 <maaku> Luke-Jr: patches welcome

19:30 GAit has joined #bitcoin-wizards

19:31 <wallet42> maaku: what kind of backpointers?

19:33 <maaku> wallet42: a merkle tree of the block nth block, mth transaction where the output being spent originated

19:34 <maaku> it's actually quite trivial, probably a dozen lines of code

19:36 <maaku> the merkle sum tree of fees is only slightly more complicated

19:37 <maaku> Luke-Jr: is you patricia trie implementation in C hosted anywhere?

19:38 GAit has quit [Quit: Leaving.]

19:38 GAit has joined #bitcoin-wizards

19:38 <Luke-Jr> maaku: never got it finished still :<

19:39 b-itcoinssg has joined #bitcoin-wizards

19:40 <zookolaptop> maaku: what do you want a patricia trie for?

19:40 zookolaptop is now known as zooko

19:40 <zooko> maaku: I mean, I see it is for this backpointer index thingie.

19:41 <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?

19:41 memymo has joined #bitcoin-wizards

19:49 GAit has quit [Quit: Leaving.]

19:57 NewLiberty has quit [Ping timeout: 260 seconds]

19:59 <maaku> no it is not for that, unrelated request :)

20:00 <maaku> it is not consensus code (for bitcoin, anyway)

20:02 <zooko> How important is concrete performance?

20:02 <zooko> I've had great success using Judy Trees for some computational linguistics hacking with my then-wife.

20:03 <zooko> Performed beautifully.

20:03 <tromp__> maaku: somewhat mature in terms of performance. but written in my overly concise and underdocumented style.

20:03 <gmaxwell> zooko: just don't read the source code for libjudy.

20:04 mpmcsweeney has joined #bitcoin-wizards

20:04 mpmcsweeney has quit [Client Quit]

20:09 <zooko> gmaxwell: oh I know.

20:09 <zooko> gmaxwell: that's why I asked what the purpose of this was before recommending it. :-)

20:11 <maaku> zooko: it woud be for consensus code (merged mining, among other things) just not on bitcoin core

20:11 adlai has quit [Ping timeout: 250 seconds]

20:11 <maaku> so clean and concise is preferred :)

20:12 <zooko> maaku: ooh, ok.

20:12 <zooko> Then I do not recommend libjudy.

20:13 voxelot has quit [Ping timeout: 240 seconds]

20:16 <zooko> I wonder what *is* the cleanest, simplest implementation of some kind of nice tree structure for such a purpose…

20:16 stevenroose_ has quit [Ping timeout: 245 seconds]

20:18 tjader has quit [Ping timeout: 276 seconds]

20:20 GGuyZ_ has joined #bitcoin-wizards

20:20 GGuyZ has quit [Read error: Connection reset by peer]

20:20 GGuyZ_ is now known as GGuyZ

20:22 dEBRUYNE has joined #bitcoin-wizards

20:22 tjader has joined #bitcoin-wizards

20:23 raedah has quit [Quit: Leaving]

20:27 ratbanebo has joined #bitcoin-wizards

20:28 phiche has quit [Quit: Leaving.]

20:29 NewLiberty has joined #bitcoin-wizards

20:35 kefkius has joined #bitcoin-wizards

20:36 voxelot has joined #bitcoin-wizards

20:53 Cory has quit [Ping timeout: 276 seconds]

20:53 ozanyurt_ has joined #bitcoin-wizards

20:56 GAit has joined #bitcoin-wizards

20:56 ozanyurt has quit [Ping timeout: 250 seconds]

21:01 justanotheruser has quit [Ping timeout: 250 seconds]

21:01 Cory has joined #bitcoin-wizards

21:03 adlie is now known as adlai

21:06 justanotheruser has joined #bitcoin-wizards

21:06 adlie has joined #bitcoin-wizards

21:06 <tromp__> btw, earlier versions of my Go counting code used judy arrays

21:07 <tromp__> back when the data sets all fit in main memory

21:08 phiche has joined #bitcoin-wizards

21:09 bramc has joined #bitcoin-wizards

21:09 bramc is now known as Guest76435

21:10 ozanyurt has joined #bitcoin-wizards

21:11 justanotheruser has quit [Ping timeout: 250 seconds]

21:12 ozanyurt_ has quit [Read error: Connection reset by peer]

21:17 justanotheruser has joined #bitcoin-wizards

21:22 <maaku> zooko yeah I'm assuming we'll have to roll our own

21:23 <maaku> I didn't find anything in my previous search

21:24 <zooko> What programming language?

21:25 <Guest76435> I'm currently working on a patricia trie https://github.com/bramcohen/MerkleSet

21:25 GGuyZ has quit [Quit: GGuyZ]

21:25 Guest76435 is now known as bramc

21:26 NewLiberty has quit [Ping timeout: 240 seconds]

21:27 <bramc> Not sure what a judy tee is

21:29 <gmaxwell> a radix-256 trie with an implementation that is something like 30k lines of highly macrofied C code. :) Pretty fast though.

21:35 <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 ...

21:35 wallet42 has quit [Quit: Leaving.]

21:35 adam3us has quit [Quit: Leaving.]

21:36 ThomasV has joined #bitcoin-wizards

21:37 GAit has quit [Quit: Leaving.]

21:38 paveljanik has quit [Quit: Leaving]

21:38 GAit has joined #bitcoin-wizards

21:40 GAit has quit [Client Quit]

21:40 GAit has joined #bitcoin-wizards

21:40 <bramc> This sounds similar to what I'm doing, but I'm being much cruder and simpler about it

21:41 phiche has quit [Ping timeout: 276 seconds]

21:41 phiche has joined #bitcoin-wizards

21:41 <bramc> What I'm doing is a patricia trie, and has different representations but there are only two: branch and leaf

21:42 <zooko> *nod*

21:43 GAit has quit [Client Quit]

21:47 tjader has quit [Ping timeout: 276 seconds]

21:50 b-itcoinssg has quit [Quit: Connection closed for inactivity]

21:52 erasmosp_ has quit [Remote host closed the connection]

21:52 tjader has joined #bitcoin-wizards

21:53 erasmospunk has joined #bitcoin-wizards

21:53 dEBRUYNE has quit [Ping timeout: 250 seconds]

21:55 GAit has joined #bitcoin-wizards

21:56 GAit has quit [Client Quit]

21:58 erasmospunk has quit [Ping timeout: 260 seconds]

21:58 Cory has quit [Ping timeout: 250 seconds]

21:59 ratbanebo has quit [Remote host closed the connection]

21:59 ratbanebo has joined #bitcoin-wizards

22:01 GGuyZ has joined #bitcoin-wizards

22:02 Cory has joined #bitcoin-wizards

22:03 GAit has joined #bitcoin-wizards

22:03 <zooko> bramc: https://github.com/bramcohen/MerkleSet/blob/master/merkle_set.py Cool! ☺

22:03 ratbanebo has quit [Ping timeout: 250 seconds]

22:04 dEBRUYNE has joined #bitcoin-wizards

22:06 voxelot has quit [Ping timeout: 240 seconds]

22:11 ozanyurt has quit [Quit: My Mac has gone to sleep. ZZZzzz…]

22:12 adam3us has joined #bitcoin-wizards

22:12 adam3us1 has joined #bitcoin-wizards

22:12 <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.

22:13 <zooko> *nod*

22:14 phiche1 has joined #bitcoin-wizards

22:15 phiche has quit [Ping timeout: 240 seconds]

22:16 adam3us has quit [Ping timeout: 250 seconds]

22:16 voxelot has joined #bitcoin-wizards

22:17 adam3us1 has quit [Ping timeout: 260 seconds]

22:27 GGuyZ has quit [Quit: GGuyZ]

22:29 Keefe_ is now known as Keefe

22:30 erasmospunk has joined #bitcoin-wizards

22:38 justanotheruser has quit [Read error: Connection reset by peer]

22:38 voxelot has quit [Ping timeout: 240 seconds]

22:40 justanotheruser has joined #bitcoin-wizards

22:43 ratbanebo has joined #bitcoin-wizards

22:45 phiche1 has quit [Quit: Leaving.]

22:46 ThomasV has quit [Ping timeout: 250 seconds]

22:48 ratbanebo has quit [Ping timeout: 245 seconds]

22:48 voxelot has joined #bitcoin-wizards

22:50 rusty has joined #bitcoin-wizards

22:51 rusty has quit [Client Quit]

22:59 Guyver2 has quit [Read error: Connection reset by peer]

23:00 dEBRUYNE has quit [Ping timeout: 265 seconds]

23:00 wallet421 has joined #bitcoin-wizards

23:01 wallet42 has quit [Client Quit]

23:03 ozanyurt has joined #bitcoin-wizards

23:06 NewLiberty has joined #bitcoin-wizards

23:08 brg444 has quit [Quit: Page closed]

23:09 NewLiberty has quit [Read error: Connection reset by peer]

23:09 NewLiberty has joined #bitcoin-wizards

23:18 tjader has quit [Ping timeout: 276 seconds]

23:20 dEBRUYNE has joined #bitcoin-wizards

23:21 ozanyurt has quit [Read error: Connection reset by peer]

23:21 ozanyurt has joined #bitcoin-wizards

23:23 tjader has joined #bitcoin-wizards

23:24 MrHodl has quit [Read error: Connection reset by peer]

23:30 coinoperated has quit [Ping timeout: 265 seconds]

23:33 Linus_ has quit [Ping timeout: 276 seconds]

23:33 GAit has quit [Quit: Leaving.]

23:33 voxelot has quit [Ping timeout: 250 seconds]

23:37 ratbanebo has joined #bitcoin-wizards

23:41 mkarrer has quit []

23:42 ratbanebo has quit [Ping timeout: 264 seconds]

23:43 mkarrer has joined #bitcoin-wizards

23:43 voxelot has joined #bitcoin-wizards

23:47 justanotheruser has quit [Read error: Connection reset by peer]

23:48 justanotheruser has joined #bitcoin-wizards

23:49 GAit has joined #bitcoin-wizards

23:51 wallet42 has joined #bitcoin-wizards

23:55 GAit has quit [Read error: Connection reset by peer]

23:55 GAit has joined #bitcoin-wizards

23:55 memymo has quit [Quit: My Mac has gone to sleep. ZZZzzz…]

23:58 PaulCapestany has quit [Quit: .]

23:58 AaronvanW has joined #bitcoin-wizards

23:58 PaulCapestany has joined #bitcoin-wizards