08:45 <adrien> that's probably the epilogue of my memory optimization journey for this: I think the intervals in the interval tree were only 2 or 3 bytes long; that's pretty terrible and the interval tree added a huge cost for tiny savings

08:46 <adrien> I switched to bigarray that's the same length as the file and holds Int32; that makes the usage 4*input_size and the algorithm simpler (although I wouldn't have arrived to that algorithm without first using BatIMap)

08:48 <adrien> and I populate a map of BatISet.t as before so that I can easily compute their intersection

08:49 <adrien> I was kind of reluctant to actively share code for which the usage instruction started like "step 0: get 64GB of RAM"

09:24 <olle> adrien: What about moving data to database? Not possible?

09:25 <adrien> well, for starters I don't need to optimize things further because usage is down to a few gigabytes at most (and I might have some low hanging fruits which are now more noticeable)

09:25 <adrien> but more importantly, I need to loop over the array in a quadratic fashion

09:26 <olle> Pre-fetch the parts you need from db before you arrive at them? :)

09:26 <olle> But yeah, few gigs is ok then

09:37 <adrien> one possible improvement is to split that bigarray into several smaller (up to 6000 ones with my current testcases but of uneven sizes)

09:37 <adrien> which would allow to move 90% of that into a cold storage

09:38 <adrien> (cold-ish but it could be refined)

09:40 <olle> Yeah, but doesn't sound necessary anymore

09:42 <adrien> I'll probably be working parallelization next

09:42 <adrien> but not this month

10:08 <adrien> but I'll add a progress indicator

10:25 <discocaml> <darrenldl> adrien: i'm going to ask silly question which you may have already answered long ago - is the repo online?

11:25 <companion_cube> adrien: what was the max integer? Could bitvectors work?

12:32 <adrien> companion_cube: for intersection of BatISet.t? that's possible, in any case I'll probably do something for performance fairly soon because O(n²) is too painful on one of my tests and counting the number of elements in both sets can be much faster

12:33 <companion_cube> I guess you could also give a try to https://roaringbitmap.org/

12:33 <companion_cube> bitvectors, only, work better for a large set of values

12:33 <adrien> and the code is at https://gitlab.com/adrien-n/compsort/ but it's completely lacking documentation, is ugly, contains various weird things/attempts to limit memory usage, and you can still see the first version was shell script

12:34 <adrien> oh, I could look at them indeed; I remember seeing them a few months ago and thinking I definitely didn't have a use for them :P

12:35 <adrien> but I might not have concerns about memory usage here

12:35 <adrien> the first step is a modified run of "xz" which takes a lot of memory (10 * input_size) and if my program doesn't use more, it's not going to be a bottleneck

12:36 <adrien> (a future change is to implement a match finder; this might reduce the memory usage, in which case it might make sense to revisit other steps)

12:37 <adrien> and basically, the program is about optimizing the order of files in archives that are to be compressed; there can be some significant gains and for distributions, it is an operation that can be done very infrequently

12:42 <adrien> companion_cube: but roaring bitmaps could reduce memory usage by a lot; I'll have to compare the CPU time

12:42 <companion_cube> reducing memory => reducing time, often

12:54 <adrien> yup but in this case I think I need a bigarray of the same size as my first bigarray, then for a small-ish range of the first bigarray, store 1 in corresponding cells of the second bigarray, then for another small-ish range of the first bigarray, look for 1s in corresponding cells of the second bigarray and count how many matches there are

12:54 <adrien> that's 2*k where k is the average size of files in the archive, which is fairly small

12:56 <adrien> and overall that should be like going through one of these bigarrays twice only

18:09 <discocaml> <darrenldl> oh wew, getting started with eio takes quite a bit of elbow grease