00:00:01  * ircretaryquit (Remote host closed the connection)
00:00:09  * ircretaryjoined
01:04:42  * phatedjoined
01:09:08  * phatedquit (Ping timeout: 246 seconds)
01:23:01  * pfrazequit (Remote host closed the connection)
01:37:22  * phatedjoined
01:46:41  * mrgodfreyjoined
01:50:43  * pfrazejoined
02:13:06  <mikolalysenko>ogd: I don't think you can do it in less than O(n) bits
02:13:30  <mikolalysenko>ogd: because if you could solve this problem, you could solve the disjointness problem
02:13:41  <mikolalysenko>and disjointness requires Omega(n) bits
02:16:34  <ogd>mikolalysenko: hm what do you mean by 'bit' there?
02:17:24  <mikolalysenko>1 yes/no value
02:17:28  <mikolalysenko>or 1/8 of a byte
02:18:04  <ogd>mikolalysenko: ah ok
02:18:23  <ogd>mikolalysenko: and n is the number of nodes total?
02:18:29  <mikolalysenko>yes
02:21:44  <ogd>mikolalysenko: so i guess our problem is actually indexing (or maybe we should be using the word decomposing?) the graph in an incremental way, such that we can efficiently query the index to establish which parts of the graph are in sync
02:24:11  <mikolalysenko>I would approach it as small set disjointness
02:24:23  <mikolalysenko>given you have some new nodes, find out what is missing
03:15:09  * mrgodfreyquit (Quit: Lost terminal)
03:41:04  * phatedquit (Remote host closed the connection)
03:41:36  * phatedjoined
03:46:21  * phatedquit (Ping timeout: 265 seconds)
04:35:48  * pfrazequit (Remote host closed the connection)
04:38:48  * ahdinosaurquit (Ping timeout: 268 seconds)
04:43:55  * phatedjoined
04:51:09  * phatedquit (Remote host closed the connection)
05:36:00  * phatedjoined
05:36:28  * phatedquit (Remote host closed the connection)
05:59:58  * phatedjoined
06:00:09  * phatedquit (Remote host closed the connection)
06:35:21  * fotoveritequit (Quit: fotoverite)
07:30:27  * stagasjoined
07:48:37  <jjjohnny_>https://github.com/mattdesl/svg-mesh-3d
08:00:38  * phatedjoined
08:05:17  * phatedquit (Ping timeout: 250 seconds)
08:25:31  * AndreasMadsenjoined
09:14:22  * djcoinjoined
09:17:54  * AndreasMadsenquit
09:44:38  * contrahaxjoined
10:00:44  * phatedjoined
10:05:46  * phatedquit (Ping timeout: 265 seconds)
10:28:00  * peutetrejoined
11:13:08  * contrahaxquit (Quit: Sleeping)
11:31:52  * djcoinquit (Quit: WeeChat 1.0.1)
12:09:11  * AndreasMadsenjoined
12:30:23  * peutetrequit (Quit: ...)
12:58:01  * peutetrejoined
13:01:02  * peutetrequit (Client Quit)
13:01:58  * peutetrejoined
13:03:41  * posejoined
13:42:51  * stagasquit (Ping timeout: 250 seconds)
13:56:29  * stagasjoined
14:31:12  * pfrazejoined
14:50:57  * AndreasMadsenquit
14:53:11  * stagasquit (Ping timeout: 240 seconds)
14:53:52  * stagasjoined
14:58:24  * pfrazequit (Remote host closed the connection)
14:58:58  * stagasquit (Remote host closed the connection)
15:00:37  * fotoveritejoined
15:05:07  * stagasjoined
15:16:33  * posequit (Remote host closed the connection)
15:17:07  * posejoined
15:21:39  * posequit (Ping timeout: 260 seconds)
15:29:22  * stagasquit (Ping timeout: 255 seconds)
15:55:51  * peutetrequit (Quit: ...)
16:01:00  * posejoined
16:04:52  * pfrazejoined
16:17:56  * posequit (Remote host closed the connection)
17:21:15  * shamajoined
17:26:02  <mikolalysenko>mafintosh: ogd what if you approach this problem at a slightly lower level
17:26:19  <mikolalysenko>say you forget about the dag, but instead you just want to synchronize the set of blobs on two machines
17:26:56  <mikolalysenko>do you think that you could do this in O((log n)* |size of diff|) round trips?
17:36:22  <mikolalysenko>maybe there is a way to do this using a trie
17:44:08  <mikolalysenko>suppose that you stick every blob into a trie, keyed by the hash of that blob
17:44:27  <mikolalysenko>then you can just diff these tries in rounds
17:44:45  <mikolalysenko>so you can check if any two subtries are equal in O(1) by comparing hashes
17:45:06  <mikolalysenko>and then use a divide and conquer/recursive strategy to find the parts of the tries where they differ
17:45:23  <mikolalysenko>hell, you could even make all this immutable too
17:51:35  * AndreasMadsenjoined
17:54:23  <mafintosh>mikolalysenko: could you give me a pratical example of the trie idea?
17:54:49  <mikolalysenko>I could write up a proof of concept tonight, but have to finish up some work right now
17:55:23  <mikolalysenko>but idea is similar to the following: https://en.wikipedia.org/wiki/Radix_tree
17:55:37  <mikolalysenko>where the strings you are inserting are hashes of blobs
17:56:18  <mikolalysenko>or look up trie merging in a book
17:56:32  <mikolalysenko>https://en.wikipedia.org/wiki/Trie
17:57:23  <mikolalysenko>basically implement blob store using trie, then implement the dag on top of the blob store
17:57:37  <ogd>oh yea i was actually thinking about prefix trees yesterday
18:00:10  * contrahaxjoined
18:00:22  * sethvincentjoined
18:03:49  <mafintosh>mikolalysenko: so a trie node would have at max 256 children?
18:03:56  <mikolalysenko>sure, if you like
18:04:00  <mikolalysenko>it can be any number
18:04:14  <mikolalysenko>if you use 2 they are called crit-bit-trees for example
18:04:26  <mafintosh>mikolalysenko: i mean in the case where you insert hashes
18:22:51  <pfraze>ogd: hey what makes chromium take so long to compile?
18:23:03  <ogd>pfraze: its a gigantic c++ project
18:23:25  <pfraze>ogd: but something like ubuntu isnt crazy like that, is it?
18:23:47  <ogd>pfraze: well ubuntu is a bunch of small to medium c/c++ projects i think
18:25:30  <pfraze>ogd: hm. just curious if that's due to project kludge, or if it's inevitable for a project like that
18:25:42  <ogd>pfraze: oh i think its totally googles fault
18:25:57  <ogd>pfraze: they have a crazy distributed build tool that google engineers can use internally so its not a problem for them
18:26:11  <pfraze>ogd: right, so they let it get ugly
18:26:14  <ogd>pfraze: they could do it differently so its easier for normal humans to work on it but they dont
18:26:23  <mikolalysenko>mafintosh: when you insert a hash into a tree, you just update nodes along the root->leaf path
18:26:35  <mikolalysenko>so there are at most log_B(n) of those
18:26:52  <mikolalysenko>where B is proportional to the size of a chunk
18:27:03  <mikolalysenko>so might be 256 or so
18:38:16  * contrahaxquit (Quit: Sleeping)
18:43:17  * phatedjoined
18:43:43  * sethvincentquit (Ping timeout: 260 seconds)
18:49:13  * paul_irish_changed nick to paul_irish
18:59:15  * contrahaxjoined
19:52:57  * sethvincentjoined
20:20:33  * knownasilyajoined
21:48:21  * eyeforeigneyejoined
21:48:36  * eyeforeigneyequit (Client Quit)
22:07:54  * AndreasMadsenquit
23:12:38  * contrahaxquit (Quit: Sleeping)
23:35:39  * pfrazequit (Remote host closed the connection)
23:54:18  * shamaquit (Quit: (╯°□°)╯︵ɐɯɐɥs)