Re: LZ4 decompression at CTFE

2016-04-28 Thread Stefan Koch via Digitalmars-d-announce

On Thursday, 28 April 2016 at 20:12:58 UTC, Stefan Koch wrote:
On Wednesday, 27 April 2016 at 06:55:46 UTC, Walter Bright 
wrote:


Sounds nice. I'm curious how it would compare to:

https://www.digitalmars.com/sargon/lz77.html

https://github.com/DigitalMars/sargon/blob/master/src/sargon/lz77.d


lz77 took 176 hnecs uncompressing
lz4 took 92 hnecs uncompressing

And another test in reversed order using the same data.

lz4 took 162 hnecs uncompressing
lz77 took 245 hnecs uncompressing


Though the compression ratio is worse.
But that is partially fixable.


Re: LZ4 decompression at CTFE

2016-04-28 Thread Stefan Koch via Digitalmars-d-announce

On Wednesday, 27 April 2016 at 06:55:46 UTC, Walter Bright wrote:


Sounds nice. I'm curious how it would compare to:

https://www.digitalmars.com/sargon/lz77.html

https://github.com/DigitalMars/sargon/blob/master/src/sargon/lz77.d


lz77 took 176 hnecs uncompressing
lz4 took 92 hnecs uncompressing

And another test in reversed order using the same data.

lz4 took 162 hnecs uncompressing
lz77 took 245 hnecs uncompressing




Re: LZ4 decompression at CTFE

2016-04-28 Thread Stefan Koch via Digitalmars-d-announce
On Thursday, 28 April 2016 at 17:29:05 UTC, Dmitry Olshansky 
wrote:


Compression on the other hand might be helpful to avoid 
precompressing everything beforehand.


I fear that is going to be pretty slow and will eat at least 1.5 
the memory of the file you are trying to store.

If you want a good compression ratio.

then again... it might be fast enough to still be useful.



Re: LZ4 decompression at CTFE

2016-04-28 Thread Stefan Koch via Digitalmars-d-announce

On Thursday, 28 April 2016 at 18:31:25 UTC, deadalnix wrote:


Also, the damn thing is allocation in a loop.


I would like a have an allocation primitive for ctfe use.
But that would not help too much as I don't know the size I need 
in advance.
storing that in the header is optional, and unfortunately lz4c 
does not store it by default.


decompressing the lz family takes never more space then 
uncompressed size of the data.
The working set is often bounded. In the case of lz4 it's 
restricted to 4k in the frame format.

and to 64k by design.




Re: LZ4 decompression at CTFE

2016-04-28 Thread Dmitry Olshansky via Digitalmars-d-announce

On 28-Apr-2016 21:31, deadalnix wrote:

On Thursday, 28 April 2016 at 17:58:50 UTC, Stefan Koch wrote:

On Thursday, 28 April 2016 at 17:29:05 UTC, Dmitry Olshansky wrote:


What's the benefit? I mean after CTFE-decompression they are going to
add weight to the binary as much as decompressed files.

Compression on the other hand might be helpful to avoid
precompressing everything beforehand.


The compiler can load files faster, that are being used by ctfe only.
Which would be stripped out by the linker later.
And keep in mind that it also works at runtime.

Memory is scarce at compiletime and this can help reducing the memory
requirements. When a bit of structure is added on top.


Considering the speed and memory consumption of CTFE, I'd bet on the
exact reverse.


Yeah, the whole CTFE to save compile-time memory sounds like a bad joke 
to me;)


Also, the damn thing is allocation in a loop.




--
Dmitry Olshansky


Re: LZ4 decompression at CTFE

2016-04-28 Thread deadalnix via Digitalmars-d-announce

On Thursday, 28 April 2016 at 17:58:50 UTC, Stefan Koch wrote:
On Thursday, 28 April 2016 at 17:29:05 UTC, Dmitry Olshansky 
wrote:


What's the benefit? I mean after CTFE-decompression they are 
going to add weight to the binary as much as decompressed 
files.


Compression on the other hand might be helpful to avoid 
precompressing everything beforehand.


The compiler can load files faster, that are being used by ctfe 
only.

Which would be stripped out by the linker later.
And keep in mind that it also works at runtime.

Memory is scarce at compiletime and this can help reducing the 
memory requirements. When a bit of structure is added on top.


Considering the speed and memory consumption of CTFE, I'd bet on 
the exact reverse.


Also, the damn thing is allocation in a loop.



Re: LZ4 decompression at CTFE

2016-04-28 Thread Stefan Koch via Digitalmars-d-announce

On Thursday, 28 April 2016 at 06:03:46 UTC, Marco Leise wrote:


There exist some comparisons for the C++ implementations
(zlib's DEFLATE being a variation of lz77):
http://catchchallenger.first-world.info//wiki/Quick_Benchmark:_Gzip_vs_Bzip2_vs_LZMA_vs_XZ_vs_LZ4_vs_LZO
https://pdfs.semanticscholar.org/9b69/86f2fff8db7e080ef8b02aa19f3941a61a91.pdf 
(pg.9)

The high compression variant of lz4 basically like gzip with 9x 
faster decompression. That makes it well suited for use cases 
where you compress once, decompress often and I/O sequential 
reads are fast e.g. 200 MB/s or the program does other 
computations meanwhile and one doesn't want decompression to 
use a lot of CPU time.


Thanks for the 2. link you posted.
This made me aware of a few things I were not aware of before.



Re: LZ4 decompression at CTFE

2016-04-28 Thread Marco Leise via Digitalmars-d-announce
Am Tue, 26 Apr 2016 23:55:46 -0700
schrieb Walter Bright :

> On 4/26/2016 3:05 PM, Stefan Koch wrote:
> > Hello,
> >
> > originally I want to wait with this announcement until DConf.
> > But since I working on another toy. I can release this info early.
> >
> > So as per title. you can decompress .lz4 flies created by the standard lz4hc
> > commnadline tool at compile time.
> >
> > No github link yet as there is a little bit of cleanup todo :)
> >
> > Please comment.  
> 
> Sounds nice. I'm curious how it would compare to:
> 
> https://www.digitalmars.com/sargon/lz77.html
> 
> https://github.com/DigitalMars/sargon/blob/master/src/sargon/lz77.d

There exist some comparisons for the C++ implementations
(zlib's DEFLATE being a variation of lz77):
http://catchchallenger.first-world.info//wiki/Quick_Benchmark:_Gzip_vs_Bzip2_vs_LZMA_vs_XZ_vs_LZ4_vs_LZO
https://pdfs.semanticscholar.org/9b69/86f2fff8db7e080ef8b02aa19f3941a61a91.pdf 
(pg.9)

The high compression variant of lz4 basically like gzip with
9x faster decompression. That makes it well suited for use
cases where you compress once, decompress often and I/O
sequential reads are fast e.g. 200 MB/s or the program does
other computations meanwhile and one doesn't want
decompression to use a lot of CPU time.

-- 
Marco



Re: LZ4 decompression at CTFE

2016-04-27 Thread Stefan Koch via Digitalmars-d-announce

On Wednesday, 27 April 2016 at 07:51:30 UTC, Dejan Lekic wrote:
That is brilliant! I need LZ4 compression for a small project I 
work on...


The decompressor is ready to be released.
It should work for all files compressed with the vanilla
lz4c -9

please regard this release as alpha quality.

https://github.com/UplinkCoder/lz4-ctfe

P.S and I did not tweak the source. The compressed file size just 
happens to be 1911.

I take this as a sign of correctness.

P.P.S Actually LZ4 is a much more interesting topic then SQLite.
If you don't mind I am going to talk about that :)




Re: LZ4 decompression at CTFE

2016-04-27 Thread Dejan Lekic via Digitalmars-d-announce

On Tuesday, 26 April 2016 at 22:05:39 UTC, Stefan Koch wrote:

Hello,

originally I want to wait with this announcement until DConf.
But since I working on another toy. I can release this info 
early.


So as per title. you can decompress .lz4 flies created by the 
standard lz4hc commnadline tool at compile time.


No github link yet as there is a little bit of cleanup todo :)

Please comment.


That is brilliant! I need LZ4 compression for a small project I 
work on...


Re: LZ4 decompression at CTFE

2016-04-27 Thread Walter Bright via Digitalmars-d-announce

On 4/26/2016 3:05 PM, Stefan Koch wrote:

Hello,

originally I want to wait with this announcement until DConf.
But since I working on another toy. I can release this info early.

So as per title. you can decompress .lz4 flies created by the standard lz4hc
commnadline tool at compile time.

No github link yet as there is a little bit of cleanup todo :)

Please comment.


Sounds nice. I'm curious how it would compare to:

https://www.digitalmars.com/sargon/lz77.html

https://github.com/DigitalMars/sargon/blob/master/src/sargon/lz77.d


Re: LZ4 decompression at CTFE

2016-04-26 Thread Stefan Koch via Digitalmars-d-announce

On Tuesday, 26 April 2016 at 22:07:47 UTC, MrSmith wrote:

I would like to use this instead of c++ static lib. Thanks! (I 
hope it works at runtime too).


Oh and If you could please send me a sample of a file you are 
trying to uncompress. That would be most helpful.


Re: LZ4 decompression at CTFE

2016-04-26 Thread Stefan Koch via Digitalmars-d-announce

On Tuesday, 26 April 2016 at 22:07:47 UTC, MrSmith wrote:
I would like to use this instead of c++ static lib. Thanks! (I 
hope it works at runtime too).


Sure it does, but keep in mind the c++ version is heavily 
optimized.
I would have to make a special runtime version to archive 
comparable performance I think.


That said,
I already plan to write another optimized version.

Concerning compression.
I am fairly certain I can beat the compression ratio of lz4hc in 
a few cases.

But it is going to be slower.


Re: LZ4 decompression at CTFE

2016-04-26 Thread MrSmith via Digitalmars-d-announce

On Tuesday, 26 April 2016 at 22:05:39 UTC, Stefan Koch wrote:

Hello,

originally I want to wait with this announcement until DConf.
But since I working on another toy. I can release this info 
early.


So as per title. you can decompress .lz4 flies created by the 
standard lz4hc commnadline tool at compile time.


No github link yet as there is a little bit of cleanup todo :)

Please comment.


I would like to use this instead of c++ static lib. Thanks! (I 
hope it works at runtime too).