www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Help optimizing UnCompress for gzipped files

reply =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
Hi all,

over the holidays, I played around with processing some gzipped json
data. First version was implemented in ruby, but took too long, so I
tried, dlang. This was already faster, but not really satisfactory fast.
Then I wrote another version in java, which was much faster.

After this I analyzed the first step of the process (gunzipping the data
from a file to memory), and found out, that dlangs UnCompress is much
slower than java, and ruby and plain c.

There was some discussion on the forum a while ago:
http://forum.dlang.org/thread/pihxxhjgnveulcdtadvg forum.dlang.org

The code I used and the numbers I got are here:
https://github.com/gizmomogwai/benchmarks/tree/master/gunzip

I used an i7 macbook with os x 10.13.2, ruby 2.5.0 built via rvm,
python3 installed by homebrew, builtin clang compiler, ldc-1.7.0-beta1,
java 1.8.0_152.

Is there anything I can do to speed up the dlang stuff?

Thanks in advance,
Christian
Jan 02 2018
next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 2 January 2018 at 10:27:11 UTC, Christian Köstlin 
wrote:

 Hi all,

 over the holidays, I played around with processing some gzipped 
 json data. First version was implemented in ruby, but took too 
 long, so I tried, dlang. This was already faster, but not 
 really satisfactory fast. Then I wrote another version in java, 
 which was much faster.

 After this I analyzed the first step of the process (gunzipping 
 the data from a file to memory), and found out, that dlangs 
 UnCompress is much slower than java, and ruby and plain c.

 There was some discussion on the forum a while ago: 
 http://forum.dlang.org/thread/pihxxhjgnveulcdtadvg forum.dlang.org

 The code I used and the numbers I got are here: 
 https://github.com/gizmomogwai/benchmarks/tree/master/gunzip

 I used an i7 macbook with os x 10.13.2, ruby 2.5.0 built via 
 rvm, python3 installed by homebrew, builtin clang compiler, 
 ldc-1.7.0-beta1, java 1.8.0_152.

 Is there anything I can do to speed up the dlang stuff?

 Thanks in advance,
 Christian


Yes indeed. You can make it much faster by using a sliced static 
array as buffer.
I suspect that most of the slowdown is caused by the gc.
As there should be only calls to the gzip library
Jan 02 2018
parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Tuesday, 2 January 2018 at 11:22:06 UTC, Stefan Koch wrote:

 You can make it much faster by using a sliced static array as 
 buffer.


Only if you want data corruption! It keeps a copy of your pointer 
internally: 
https://github.com/dlang/phobos/blob/master/std/zlib.d#L605

It also will always overallocate new buffers on each call 
<https://github.com/dlang/phobos/blob/master/std/zlib.d#L602>

There is no efficient way to use it. The implementation is 
substandard because the API limits the design.

If we really want a fast std.zlib, the API will need to be 
extended with new functions to fix these. Those new functions 
will probably look a LOT like the underlying C functions... which 
is why I say just use them right now.


 I suspect that most of the slowdown is caused by the gc.
 As there should be only calls to the gzip library


plz measure before spreading FUD about the GC.
Jan 02 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/2/18 8:57 AM, Adam D. Ruppe wrote:

 On Tuesday, 2 January 2018 at 11:22:06 UTC, Stefan Koch wrote:

 You can make it much faster by using a sliced static array as buffer.


 
 Only if you want data corruption! It keeps a copy of your pointer 
 internally: https://github.com/dlang/phobos/blob/master/std/zlib.d#L605
 
 It also will always overallocate new buffers on each call 
 <https://github.com/dlang/phobos/blob/master/std/zlib.d#L602>
 
 There is no efficient way to use it. The implementation is substandard 
 because the API limits the design.


iopipe handles this quite well. And deals with the buffers properly 
(yes, it is very tricky. You have to ref-count the zstream structure, 
because it keeps internal pointers to *itself* as well!). And no, iopipe 
doesn't use std.zlib, I use the etc.zlib functions (but I poached some 
ideas from std.zlib when writing it).

https://github.com/schveiguy/iopipe/blob/master/source/iopipe/zip.d

I even wrote a json parser for iopipe. But it's far from complete. And 
probably needs updating since I changed some of the iopipe API.

https://github.com/schveiguy/jsoniopipe

Depending on the use case, it might be enough, and should be very fast.

-Steve
Jan 02 2018
parent reply =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
On 02.01.18 15:09, Steven Schveighoffer wrote:

 On 1/2/18 8:57 AM, Adam D. Ruppe wrote:

 On Tuesday, 2 January 2018 at 11:22:06 UTC, Stefan Koch wrote:

 You can make it much faster by using a sliced static array as buffer.


 Only if you want data corruption! It keeps a copy of your pointer
 internally: https://github.com/dlang/phobos/blob/master/std/zlib.d#L605

 It also will always overallocate new buffers on each call
 <https://github.com/dlang/phobos/blob/master/std/zlib.d#L602>

 There is no efficient way to use it. The implementation is substandard
 because the API limits the design.


 
 iopipe handles this quite well. And deals with the buffers properly
 (yes, it is very tricky. You have to ref-count the zstream structure,
 because it keeps internal pointers to *itself* as well!). And no, iopipe
 doesn't use std.zlib, I use the etc.zlib functions (but I poached some
 ideas from std.zlib when writing it).
 
 https://github.com/schveiguy/iopipe/blob/master/source/iopipe/zip.d
 
 I even wrote a json parser for iopipe. But it's far from complete. And
 probably needs updating since I changed some of the iopipe API.
 
 https://github.com/schveiguy/jsoniopipe
 
 Depending on the use case, it might be enough, and should be very fast.
 
 -Steve


Thanks Steve for this proposal (actually I already had an iopipe version
on my harddisk that I applied to this problem) Its more or less your
unzip example + putting the data to an appender (I hope this is how it
should be done, to get the data to RAM).

iopipe is already better than the normal dlang version, almost like
java, but still far from the solution. I updated
https://github.com/gizmomogwai/benchmarks/tree/master/gunzip

I will give the direct gunzip calls a try ...

In terms of json parsing, I had really nice results with the fast.json
pull parser, but its comparing a little bit apples with oranges, because
I did not pull out all the data there.

---
Christian
Jan 02 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/2/18 1:01 PM, Christian Köstlin wrote:

 On 02.01.18 15:09, Steven Schveighoffer wrote:

 On 1/2/18 8:57 AM, Adam D. Ruppe wrote:

 On Tuesday, 2 January 2018 at 11:22:06 UTC, Stefan Koch wrote:

 You can make it much faster by using a sliced static array as buffer.


 Only if you want data corruption! It keeps a copy of your pointer
 internally: https://github.com/dlang/phobos/blob/master/std/zlib.d#L605

 It also will always overallocate new buffers on each call
 <https://github.com/dlang/phobos/blob/master/std/zlib.d#L602>

 There is no efficient way to use it. The implementation is substandard
 because the API limits the design.


 iopipe handles this quite well. And deals with the buffers properly
 (yes, it is very tricky. You have to ref-count the zstream structure,
 because it keeps internal pointers to *itself* as well!). And no, iopipe
 doesn't use std.zlib, I use the etc.zlib functions (but I poached some
 ideas from std.zlib when writing it).

 https://github.com/schveiguy/iopipe/blob/master/source/iopipe/zip.d

 I even wrote a json parser for iopipe. But it's far from complete. And
 probably needs updating since I changed some of the iopipe API.

 https://github.com/schveiguy/jsoniopipe

 Depending on the use case, it might be enough, and should be very fast.


 Thanks Steve for this proposal (actually I already had an iopipe version
 on my harddisk that I applied to this problem) Its more or less your
 unzip example + putting the data to an appender (I hope this is how it
 should be done, to get the data to RAM).


Well, you don't need to use appender for that (and doing so is copying a 
lot of the data an extra time). All you need is to extend the pipe until 
there isn't any more new data, and it will all be in the buffer.

// almost the same line from your current version
auto mypipe = openDev("../out/nist/2011.json.gz")
                   .bufd.unzip(CompressionFormat.gzip);

// This line here will work with the current release (0.0.2):
while(mypipe.extend(0) != 0) {}

//But I have a fix for a bug that hasn't been released yet, this would 
work if you use iopipe-master:
mypipe.ensureElems();

// getting the data is as simple as looking at the buffer.
auto data = mypipe.window; // ubyte[] of the data


 iopipe is already better than the normal dlang version, almost like
 java, but still far from the solution. I updated
 https://github.com/gizmomogwai/benchmarks/tree/master/gunzip
 
 I will give the direct gunzip calls a try ...
 
 In terms of json parsing, I had really nice results with the fast.json
 pull parser, but its comparing a little bit apples with oranges, because
 I did not pull out all the data there.


Yeah, with jsoniopipe being very raw, I wouldn't be sure it was usable 
in your case. The end goal is to have something fast, but very easy to 
construct. I wasn't planning on focusing on the speed (yet) like other 
libraries do, but ease of writing code to use it.

-Steve
Jan 02 2018
next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/2/18 3:13 PM, Steven Schveighoffer wrote:

 // almost the same line from your current version
 auto mypipe = openDev("../out/nist/2011.json.gz")
                    .bufd.unzip(CompressionFormat.gzip);


Would you mind telling me the source of the data? When I do get around 
to it, I want to have a good dataset to test things against, and would 
be good to use what others reach for.

-Steve
Jan 02 2018
parent =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
On 02.01.18 21:48, Steven Schveighoffer wrote:

 On 1/2/18 3:13 PM, Steven Schveighoffer wrote:

 // almost the same line from your current version
 auto mypipe = openDev("../out/nist/2011.json.gz")
                    .bufd.unzip(CompressionFormat.gzip);


 
 Would you mind telling me the source of the data? When I do get around
 to it, I want to have a good dataset to test things against, and would
 be good to use what others reach for.
 
 -Steve


Hi Steve,

thanks for looking into this.
I use data from nist.gov, the Makefile includes these download instructions:
    curl -s
https://static.nvd.nist.gov/feeds/json/cve/1.0/nvdcve-1.0-2011.json.gz >
out/nist/2011.json.gz`

--
Christian Köstlin
Jan 02 2018
prev sibling parent reply =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
On 02.01.18 21:13, Steven Schveighoffer wrote:

 Well, you don't need to use appender for that (and doing so is copying a
 lot of the data an extra time). All you need is to extend the pipe until
 there isn't any more new data, and it will all be in the buffer.
 
 // almost the same line from your current version
 auto mypipe = openDev("../out/nist/2011.json.gz")
                   .bufd.unzip(CompressionFormat.gzip);
 
 // This line here will work with the current release (0.0.2):
 while(mypipe.extend(0) != 0) {}


Thanks for this input, I updated the program to make use of this method
and compare it to the appender thing as well.


 I will give the direct gunzip calls a try ...




I added direct gunzip calls as well... Those are really good, as long as
I do not try to get the data into ram :) then it is "bad" again.
I wonder what the real difference to the lowlevel solution with own
appender and the c version is. For me they look almost the same (ugly,
only the performance seems to be nice).

Funny thing is, that if I add the clang address sanitizer things to the
c program, I get almost the same numbers as for java :)



 Yeah, with jsoniopipe being very raw, I wouldn't be sure it was usable
 in your case. The end goal is to have something fast, but very easy to
 construct. I wasn't planning on focusing on the speed (yet) like other
 libraries do, but ease of writing code to use it.
 
 -Steve


--
Christian Köstlin
Jan 02 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/3/18 2:47 AM, Christian Köstlin wrote:

 On 02.01.18 21:13, Steven Schveighoffer wrote:

 Well, you don't need to use appender for that (and doing so is copying a
 lot of the data an extra time). All you need is to extend the pipe until
 there isn't any more new data, and it will all be in the buffer.

 // almost the same line from your current version
 auto mypipe = openDev("../out/nist/2011.json.gz")
                    .bufd.unzip(CompressionFormat.gzip);

 // This line here will work with the current release (0.0.2):
 while(mypipe.extend(0) != 0) {}


 Thanks for this input, I updated the program to make use of this method
 and compare it to the appender thing as well.
 


Hm.. the numbers are worse! I would have expected to be at least 
comparable. I'll have to look into it. Thanks for posting this.

-Steve
Jan 03 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/3/18 9:42 AM, Steven Schveighoffer wrote:

 On 1/3/18 2:47 AM, Christian Köstlin wrote:

 On 02.01.18 21:13, Steven Schveighoffer wrote:

 Well, you don't need to use appender for that (and doing so is copying a
 lot of the data an extra time). All you need is to extend the pipe until
 there isn't any more new data, and it will all be in the buffer.

 // almost the same line from your current version
 auto mypipe = openDev("../out/nist/2011.json.gz")
                    .bufd.unzip(CompressionFormat.gzip);

 // This line here will work with the current release (0.0.2):
 while(mypipe.extend(0) != 0) {}


 Thanks for this input, I updated the program to make use of this method
 and compare it to the appender thing as well.


 
 Hm.. the numbers are worse! I would have expected to be at least 
 comparable. I'll have to look into it. Thanks for posting this.


Alright. I have spent some time examining the issues, and here are my 
findings:

1. The major differentiator between the C and D algorithms is the use of 
C realloc. This one thing saves the most time. I'm going to update 
iopipe so you can use it (stand by). I will also be examining how to 
simulate using realloc when not using C malloc in iopipe. I think it's 
the copying of data to the new buffer that is causing issues.

2. extend(0) always attempts to read 8k more bytes. The buffer extends 
by 8k by going into another couple pages. Somehow this is choking the 
algorithm. I think the cost of extending pages actually ends up hurting 
performance (something we need to look at in the GC in general).

3. extendElems should allow extending all the elements in the most 
optimal fashion. Fixing that, iopipe performs as well as the 
Appender/iopipe version. This is coming out as well.

Stay tuned, there will be updates to iopipe to hopefully make it as fast 
in this microbenchmark as the C version :)

-Steve
Jan 03 2018
next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/3/18 3:28 PM, Steven Schveighoffer wrote:

 1. The major differentiator between the C and D algorithms is the use of 
 C realloc. This one thing saves the most time. I'm going to update 
 iopipe so you can use it (stand by). I will also be examining how to 
 simulate using realloc when not using C malloc in iopipe. I think it's 
 the copying of data to the new buffer that is causing issues.


Looking at when C realloc actually moves the data, it appears it all of 
a sudden over-allocates very very large blocks, much larger than the GC 
will over-allocate. This is why the GC is losing. After a certain size, 
the GC doesn't allocate blocks to grow into, so we start copying on 
every realloc.

So it's not so much the performance of the copying, but the number of 
times copying is required that is affecting the ultimate performance.

-Steve
Jan 03 2018
parent reply =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
On 03.01.18 22:33, Steven Schveighoffer wrote:

 On 1/3/18 3:28 PM, Steven Schveighoffer wrote:

 1. The major differentiator between the C and D algorithms is the use
 of C realloc. This one thing saves the most time. I'm going to update
 iopipe so you can use it (stand by). I will also be examining how to
 simulate using realloc when not using C malloc in iopipe. I think it's
 the copying of data to the new buffer that is causing issues.


 
 Looking at when C realloc actually moves the data, it appears it all of
 a sudden over-allocates very very large blocks, much larger than the GC
 will over-allocate. This is why the GC is losing. After a certain size,
 the GC doesn't allocate blocks to grow into, so we start copying on
 every realloc.


That a very intersting finding! If I find some time today, I will also
try a pure malloc/memcpy/free solution in c and also look how many real
allocs are done. Thats funny, because this means, that this whole *2
thing for growing buffers that you learn is well taken care of in libc?
Or does it still mean, that you should allocate in a pattern like this,
for libc's algorithm to kick in? Is there api to see how much realloc
really allocated, or is it only possible by comparing pointers to see if
realloc delivers a new or the old pointer?

--
Christian  Köstlin
Jan 03 2018
parent reply =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
I added now a c variant, that does always malloc/memcpy/free. Its much
slower for sure.
Also I put some output in thats shows when a real realloc happens. Its
like you said:

did a real realloc
did a real realloc
did a real realloc
did a real realloc
did a real realloc
did a real realloc
did not a real realloc
did not a real realloc
did not a real realloc
did not a real realloc
did not a real realloc
did not a real realloc
did not a real realloc
did not a real realloc
did a real realloc
did not a real realloc

funny thing is, i do not always get the same sequence of real reallocs.


--
Christian Köstlin
Jan 04 2018
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/4/18 4:47 AM, Christian Köstlin wrote:

 I added now a c variant, that does always malloc/memcpy/free. Its much
 slower for sure.
 Also I put some output in thats shows when a real realloc happens. Its
 like you said:
 
 did a real realloc
 did a real realloc
 did a real realloc
 did a real realloc
 did a real realloc
 did a real realloc
 did not a real realloc
 did not a real realloc
 did not a real realloc
 did not a real realloc
 did not a real realloc
 did not a real realloc
 did not a real realloc
 did not a real realloc
 did a real realloc
 did not a real realloc
 
 funny thing is, i do not always get the same sequence of real reallocs.


Another thing I did was print out the size of the buffer before the 
realloc. In other words:

auto oldsize = buffer.length;
auto oldptr = buffer.ptr;
buffer = (cast(ubyte *)realloc(buffer.ptr, newsize))[0 .. newsize];
if(buffer.ptr != oldptr) writeln("moved: ", oldsize);

Even the sizes malloc chooses for its big leap are not consistent from 
run to run!

I'm wondering if possibly when you keep reallocing a large block, and it 
doesn't have enough memory, needs more from the system, it just tacks it 
onto the end of the existing big block. This would make the performance 
for this microbenchmark highly dependent on not doing any other allocations!

BTW, my numbers are consistent, but there is a difference from yours. 
For example, my C runs are about 430ms, and my fast D runs are about 
650-700ms. I never get the 200ms range runs that you are seeing. I have 
a similar machine, but still running Sierra.

-Steve
Jan 04 2018
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/3/18 3:28 PM, Steven Schveighoffer wrote:


 Stay tuned, there will be updates to iopipe to hopefully make it as fast 
 in this microbenchmark as the C version :)


v0.0.3 has been released. To take advantage of using malloc/realloc, you 
can use std.experimental.allocator.mallocator.Mallocator as the 
BufferManager's allocator.

e.g.:

auto myPipe = openDev("file.gz").bufd // not here
       .unzip!Mallocator;              // here

myPipe.ensureElems(); // this works now.

auto bytesRead = myPipe.window.length;

The reason you don't need it on the first bufd is because that is the 
buffer of the file stream, which isn't going to grow.

Note: the buffer manager does not free the data on destruction! You are 
responsible for freeing it (if you use Mallocator).

-Steve
Jan 04 2018
parent reply =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
On 04.01.18 16:53, Steven Schveighoffer wrote:

 On 1/3/18 3:28 PM, Steven Schveighoffer wrote:
 

 Stay tuned, there will be updates to iopipe to hopefully make it as
 fast in this microbenchmark as the C version :)


 
 v0.0.3 has been released. To take advantage of using malloc/realloc, you
 can use std.experimental.allocator.mallocator.Mallocator as the
 BufferManager's allocator.
 
 e.g.:
 
 auto myPipe = openDev("file.gz").bufd // not here
       .unzip!Mallocator;              // here
 
 myPipe.ensureElems(); // this works now.
 
 auto bytesRead = myPipe.window.length;
 
 The reason you don't need it on the first bufd is because that is the
 buffer of the file stream, which isn't going to grow.
 
 Note: the buffer manager does not free the data on destruction! You are
 responsible for freeing it (if you use Mallocator).


Thanks Steve,
this runs now faster, I will update the table.

Sorry, but I do not get how to cleanup the mallocated memory :)
Could you help me out here?

--
Christian Köstlin
Jan 04 2018
next sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/4/18 1:57 PM, Christian Köstlin wrote:

 Sorry, but I do not get how to cleanup the mallocated memory :)
 Could you help me out here?


free(mypipe.window.ptr);

At the moment this works because you haven't released any data from the 
front. But eventually, I will need to figure out how to handle this when 
it's not so neat.

-Steve
Jan 04 2018
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/4/18 1:57 PM, Christian Köstlin wrote:

 Thanks Steve,
 this runs now faster, I will update the table.


Still a bit irked that I can't match the C speed :/

But, I can't get your C speed to duplicate on my mac even with gcc, so 
I'm not sure where to start. I find it interesting that you are not 
using any optimization flags for gcc.

-Steve
Jan 04 2018
parent reply =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
On 04.01.18 20:46, Steven Schveighoffer wrote:

 On 1/4/18 1:57 PM, Christian Köstlin wrote:

 Thanks Steve,
 this runs now faster, I will update the table.


 
 Still a bit irked that I can't match the C speed :/
 
 But, I can't get your C speed to duplicate on my mac even with gcc, so
 I'm not sure where to start. I find it interesting that you are not
 using any optimization flags for gcc.


I guess, the code in my program is small enough that the optimize flags
do not matter... most of the stuff is pulled from libz? Which is
dynamically linked against /usr/lib/libz.1.dylib.

I also cannot understand what I should do more (will try realloc with
Mallocator) for the dlang-low-level variant to get to the c speed.
rust is doing quite well there

--
Christian Köstlin
Jan 04 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/5/18 1:01 AM, Christian Köstlin wrote:

 On 04.01.18 20:46, Steven Schveighoffer wrote:

 On 1/4/18 1:57 PM, Christian Köstlin wrote:

 Thanks Steve,
 this runs now faster, I will update the table.


 Still a bit irked that I can't match the C speed :/

 But, I can't get your C speed to duplicate on my mac even with gcc, so
 I'm not sure where to start. I find it interesting that you are not
 using any optimization flags for gcc.


 I guess, the code in my program is small enough that the optimize flags
 do not matter... most of the stuff is pulled from libz? Which is
 dynamically linked against /usr/lib/libz.1.dylib.


Yeah, I guess most of the bottlenecks are inside libz, or the memory 
allocator. There isn't much optimization to be done in the main program 
itself.


 I also cannot understand what I should do more (will try realloc with
 Mallocator) for the dlang-low-level variant to get to the c speed.


D compiles just the same as C. So theoretically you should be able to 
get the same performance with a ported version of your C code. It's 
worth a shot.


 rust is doing quite well there


I'll say a few words of caution here:

1. Almost all of these tests use the same C library to unzip. So it's 
really not a test of the performance of decompression, but the 
performance of memory management. And it appears that any test using 
malloc/realloc is in a different tier. Presumably because of the lack of 
copies (as discussed earlier).
2. Your rust test (I think, I'm not sure) is testing 2 things in the 
same run, which could potentially have dramatic consequences for the 
second test. For instance, it could already have all the required memory 
blocks ready, and the allocation strategy suddenly gets better. Or maybe 
there is some kind of caching of the input being done. I think you have 
a fairer test for the second option by running it in a separate program. 
I've never used rust, so I don't know what exactly your code is doing.
3. It's hard to make a decision based on such microbenchmarks as to 
which solution is "better" in an actual real-world program, especially 
when the state/usage of the memory allocator plays a huge role in this.

-Steve
Jan 05 2018
parent reply =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
On 05.01.18 15:39, Steven Schveighoffer wrote:

 Yeah, I guess most of the bottlenecks are inside libz, or the memory
 allocator. There isn't much optimization to be done in the main program
 itself.

 D compiles just the same as C. So theoretically you should be able to
 get the same performance with a ported version of your C code. It's
 worth a shot.


I added another version that tries to do the "same" as the c version
using mallocator, but i am still way off, perhaps its creating too many
ranges on the underlying array. but its around the same speed as your
great iopipe thing.
My solution does have the same memory leak, as I am not sure how to best
get the memory out of the FastAppender so that it is automagically
cleaned up. Perhaps if we get rc things, this gets easier?
I updated: https://github.com/gizmomogwai/benchmarks/tree/master/gunzip
with the newest numbers on my machine, but I think your iopipe solution
is the best one we can get at the moment!


 rust is doing quite well there


 
 I'll say a few words of caution here:
 
 1. Almost all of these tests use the same C library to unzip. So it's
 really not a test of the performance of decompression, but the
 performance of memory management. And it appears that any test using
 malloc/realloc is in a different tier. Presumably because of the lack of
 copies (as discussed earlier).
 2. Your rust test (I think, I'm not sure) is testing 2 things in the
 same run, which could potentially have dramatic consequences for the
 second test. For instance, it could already have all the required memory
 blocks ready, and the allocation strategy suddenly gets better. Or maybe
 there is some kind of caching of the input being done. I think you have
 a fairer test for the second option by running it in a separate program.
 I've never used rust, so I don't know what exactly your code is doing.
 3. It's hard to make a decision based on such microbenchmarks as to
 which solution is "better" in an actual real-world program, especially
 when the state/usage of the memory allocator plays a huge role in this.


sure .. thats true
Jan 05 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/5/18 3:09 PM, Christian Köstlin wrote:

 On 05.01.18 15:39, Steven Schveighoffer wrote:

 Yeah, I guess most of the bottlenecks are inside libz, or the memory
 allocator. There isn't much optimization to be done in the main program
 itself.

 D compiles just the same as C. So theoretically you should be able to
 get the same performance with a ported version of your C code. It's
 worth a shot.


 I added another version that tries to do the "same" as the c version
 using mallocator, but i am still way off, perhaps its creating too many
 ranges on the underlying array. but its around the same speed as your
 great iopipe thing.


Hm... I think really there is some magic initial state of the allocator, 
and that's what allows it to go so fast.

One thing about the D version, because druntime is also using malloc 
(the GC is backed by malloc'd data after all), the initial state of the 
heap is quite different from when you start in C. It may be impossible 
or nearly impossible to duplicate the performance. But the flipside (if 
this is indeed the case) is that you won't see the same performance in a 
real-world app anyway, even in C.

One thing to try, you preallocate the ENTIRE buffer. This only works if 
you know how many bytes it will decompress to (not always possible), but 
it will take the allocator out of the equation completely. And it's 
probably going to be the most efficient method (you aren't leaving 
behind smaller unused blocks when you realloc). If for some reason we 
can't beat/tie the C version doing that, then something else is going on.


 My solution does have the same memory leak, as I am not sure how to best
 get the memory out of the FastAppender so that it is automagically
 cleaned up. Perhaps if we get rc things, this gets easier?


I've been giving some thought to this. I think iopipe needs some buffer 
management primitives that allow you to finagle the buffer. I've been 
needing this for some time anyway (for file seeking). Right now, the 
buffer itself is buried in the chain, so it's hard to get at the actual 
buffer.

Alternatively, I probably also need to give some thought to a mechanism 
that auto-frees the memory when it can tell nobody is still using the 
iopipe. Given that iopipe's signature feature is direct buffer access, 
this would mean anything that uses such a feature would have to be unsafe.

-Steve
Jan 05 2018
parent reply =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
On 05.01.18 23:04, Steven Schveighoffer wrote:

 On 1/5/18 3:09 PM, Christian Köstlin wrote:

 On 05.01.18 15:39, Steven Schveighoffer wrote:

 Yeah, I guess most of the bottlenecks are inside libz, or the memory
 allocator. There isn't much optimization to be done in the main program
 itself.

 D compiles just the same as C. So theoretically you should be able to
 get the same performance with a ported version of your C code. It's
 worth a shot.


 I added another version that tries to do the "same" as the c version
 using mallocator, but i am still way off, perhaps its creating too many
 ranges on the underlying array. but its around the same speed as your
 great iopipe thing.


 
 Hm... I think really there is some magic initial state of the allocator,
 and that's what allows it to go so fast.
 
 One thing about the D version, because druntime is also using malloc
 (the GC is backed by malloc'd data after all), the initial state of the
 heap is quite different from when you start in C. It may be impossible
 or nearly impossible to duplicate the performance. But the flipside (if
 this is indeed the case) is that you won't see the same performance in a
 real-world app anyway, even in C.
 
 One thing to try, you preallocate the ENTIRE buffer. This only works if
 you know how many bytes it will decompress to (not always possible), but
 it will take the allocator out of the equation completely. And it's
 probably going to be the most efficient method (you aren't leaving
 behind smaller unused blocks when you realloc). If for some reason we
 can't beat/tie the C version doing that, then something else is going on.


yes ... this is something i forgot to try out ... will do now :)
mhh .. interesting numbers ... c is even faster, my d lowlevel solution
is also a little bit faster, but much slower than the no copy version
(funnily, no copy is the wrong name, it just overwrites all the data in
a small buffer).


 My solution does have the same memory leak, as I am not sure how to best
 get the memory out of the FastAppender so that it is automagically
 cleaned up. Perhaps if we get rc things, this gets easier?


 
 I've been giving some thought to this. I think iopipe needs some buffer
 management primitives that allow you to finagle the buffer. I've been
 needing this for some time anyway (for file seeking). Right now, the
 buffer itself is buried in the chain, so it's hard to get at the actual
 buffer.
 
 Alternatively, I probably also need to give some thought to a mechanism
 that auto-frees the memory when it can tell nobody is still using the
 iopipe. Given that iopipe's signature feature is direct buffer access,
 this would mean anything that uses such a feature would have to be unsafe.


yes .. thats tricky ...
one question about iopipe. is it possible to transform the elements in
the pipe as well ... e.g. away from a buffer of bytes to json objects?

--
Christian Köstlin
Jan 06 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/6/18 11:14 AM, Christian Köstlin wrote:

 On 05.01.18 23:04, Steven Schveighoffer wrote:

 One thing to try, you preallocate the ENTIRE buffer. This only works if
 you know how many bytes it will decompress to (not always possible), but
 it will take the allocator out of the equation completely. And it's
 probably going to be the most efficient method (you aren't leaving
 behind smaller unused blocks when you realloc). If for some reason we
 can't beat/tie the C version doing that, then something else is going on.


 yes ... this is something i forgot to try out ... will do now :)
 mhh .. interesting numbers ... c is even faster, my d lowlevel solution
 is also a little bit faster, but much slower than the no copy version
 (funnily, no copy is the wrong name, it just overwrites all the data in
 a small buffer).


Not from what I'm reading, the C solution is about the same (257 vs. 
261). Not sure if you have averaged these numbers, especially on a real 
computer that might be doing other things.

Note: I would expect it to be a tiny bit faster, but not monumentally 
faster. From my testing with the reallocation, it only reallocates a 
large quantity of data once.

However, the D solution should be much faster. Part of the issue is that 
you still aren't low-level enough :)

Instead of allocating the ubyte array with this line:

ubyte[] buffer = new ubyte[200*1024*1024];

Try this instead:

// from std.array
auto buffer = uninitializedArray!(ubyte[], 200*1024*1024);

The difference is that the first one will have the runtime 0-initialize 
all the data.


 one question about iopipe. is it possible to transform the elements in
 the pipe as well ... e.g. away from a buffer of bytes to json objects?


Yes! I am working on doing just that, but haven't had a chance to update 
the toy project I wrote: https://github.com/schveiguy/jsoniopipe

I was planning actually on having an iopipe of JsonItem, which would 
work just like a normal buffer, but reference the ubyte buffer underneath.

Eventually, the final product should have a range of JsonValue, which 
you would recurse into in order to parse its children. All of it will be 
lazy, and stream-based, so you don't have to load the whole file if it's 
huge.

Note, you can't have an iopipe of JsonValue, because it's a recursive 
format. JsonItems are just individual defined tokens, so they can be linear.

-Steve
Jan 07 2018
parent =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
On 07.01.18 14:44, Steven Schveighoffer wrote:

 Not from what I'm reading, the C solution is about the same (257 vs.
 261). Not sure if you have averaged these numbers, especially on a real
 computer that might be doing other things.


yes you are right ... for proper benchmarking proper statistics should
be in place, taking out extreme values, averaging them, ...


 Note: I would expect it to be a tiny bit faster, but not monumentally
 faster. From my testing with the reallocation, it only reallocates a
 large quantity of data once.
 
 However, the D solution should be much faster. Part of the issue is that
 you still aren't low-level enough :)
 
 Instead of allocating the ubyte array with this line:
 
 ubyte[] buffer = new ubyte[200*1024*1024];
 
 Try this instead:
 
 // from std.array
 auto buffer = uninitializedArray!(ubyte[], 200*1024*1024);


thanks for that ... i just did not know how to get an uninitialized
array. i was aware, that dlang is nice and puts init there :)


 Yes! I am working on doing just that, but haven't had a chance to update
 the toy project I wrote: https://github.com/schveiguy/jsoniopipe
 
 I was planning actually on having an iopipe of JsonItem, which would
 work just like a normal buffer, but reference the ubyte buffer underneath.
 
 Eventually, the final product should have a range of JsonValue, which
 you would recurse into in order to parse its children. All of it will be
 lazy, and stream-based, so you don't have to load the whole file if it's
 huge.
 
 Note, you can't have an iopipe of JsonValue, because it's a recursive
 format. JsonItems are just individual defined tokens, so they can be
 linear.


sounds really good. i played around with
https://github.com/mleise/fast/blob/master/source/fast/json.d ... thats
an interesting pull parser with the wrong licence unfortunately ... i
wonder if something like this could be done on top of iopipe instead of
a "real" buffer.

---
Christian Köstlin
Jan 09 2018
prev sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Tuesday, 2 January 2018 at 10:27:11 UTC, Christian Köstlin 
wrote:

 After this I analyzed the first step of the process (gunzipping 
 the data from a file to memory), and found out, that dlangs 
 UnCompress is much slower than java, and ruby and plain c.


Yeah, std.zlib is VERY poorly written. You can get much better 
performance by just calling the C functions yourself instead. 
(You can just import import etc.c.zlib; it is included still)

Improving it would mean changing the public API. I think the 
one-shot compress/uncompress functions are ok, but the streaming 
class does a lot of unnecessary work inside like copying stuff 
around.
Jan 02 2018
parent =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
On 02.01.18 14:51, Adam D. Ruppe wrote:

 On Tuesday, 2 January 2018 at 10:27:11 UTC, Christian Köstlin wrote:

 After this I analyzed the first step of the process (gunzipping the
 data from a file to memory), and found out, that dlangs UnCompress is
 much slower than java, and ruby and plain c.


 
 Yeah, std.zlib is VERY poorly written. You can get much better
 performance by just calling the C functions yourself instead. (You can
 just import import etc.c.zlib; it is included still)
 
 Improving it would mean changing the public API. I think the one-shot
 compress/uncompress functions are ok, but the streaming class does a lot
 of unnecessary work inside like copying stuff around.


I added a version that uses the gzip lowlevel apis (similar to my
example c program). I am still having problems copying the data fast
enough to an dlang array.

please see the updated page:
https://github.com/gizmomogwai/benchmarks/tree/master/gunzip

--
Christian Köstlin
Jan 02 2018