On Saturday, 21 May 2016 at 22:41:49 UTC, Guillaume Boucher wrote:
>  It's almost as if using information about the actual data leads to a better compression scheme.

Exactly. It always is. Since you know where to look for redundancy instead of blindly comparing bytes.

On 5/21/2016 3:41 PM, Guillaume Boucher wrote:
> Sorry if I didn't memorize everything in this forum from the last 20 years, can
> you give a link to some reasoning?

DMC++ matches the Microsoft name mangling scheme, which includes such compression. It proved hopelessly inadequate, which is why I implemented compress.c in the first place (it was for the DMC++ compiler).

(And frankly, I don't see how an ad-hoc scheme like that could hope to compare with a real compression algorithm.)

On Saturday, 21 May 2016 at 22:01:40 UTC, Walter Bright wrote:
> Give it a try, see if it pans out.
>
> Other possibilities are the lookback dictionary is fixed at 1023 characters. Experimenting and benchmarking can indicate if it should be more or less. Perhaps 512 will yield just as good compression on real world identifier strings.
>
> Or try another scheme entirely, like huffman coding.

 I'm going to try for a lookback and scan which uses quite a bit of memory. On the other hand you can reuse the memory over and over again, so that isn't an issue. Although it will take up a Meg in memory. Also written entirely in D, so...

 I think I'll go with a similar setup you have for the encoding (3 bytes). Should be nearly identical in output.

On 5/21/2016 5:52 PM, Era Scarecrow wrote:
>  I'm going to try for a lookback and scan which uses quite a bit of memory. On
> the other hand you can reuse the memory over and over again, so that isn't an
> issue. Although it will take up a Meg in memory. Also written entirely in D, so...
>
>  I think I'll go with a similar setup you have for the encoding (3 bytes).
> Should be nearly identical in output.

Just a note: large lookup tables can have cold cache performance problems.

On Sunday, 22 May 2016 at 01:36:39 UTC, Walter Bright wrote:
> On 5/21/2016 5:52 PM, Era Scarecrow wrote:
>>  I'm going to try for a lookback and scan which uses quite a bit of memory.
>
> Just a note: large lookup tables can have cold cache performance problems.

 I know, if it doesn't fit in 64k then you can't rely on the cache...

On Sunday, 22 May 2016 at 01:46:23 UTC, Era Scarecrow wrote:
>  I know, if it doesn't fit in 64k then you can't rely on the cache...

 Finished. It's blazing fast and even compresses in my test example as good or better than gzip/zlib (although maybe that's because it's headerless).

 Now I just need to stress test it against some really large input and check for failures. Regardless it has a compression and decompression functions, along with benchmarking it vs the compression algorithm I'm trying to beat.

On 22/5/2016 05:51, Stefan Koch wrote:
> On Saturday, 21 May 2016 at 21:12:15 UTC, Walter Bright wrote:
>> The current one is effective, but slow:
>>
>> https://github.com/dlang/dmd/blob/master/src/backend/compress.c
>>
>> Anyone want to make a stab at making it faster? Changing the format is
>> fair game, as well as down and dirty assembler if that's what it takes.
>>
>> So really, how good are you at fast code?
>
> Is LZ4 acceptable ?
> If so the current C implementation is hard to beat.
> And maybe it's best to just copy it in.

Agree. I've had the best results with LZ4. We can either link to the C code, or port it to D. It's very trivial.

L.

On Sunday, 22 May 2016 at 04:35:15 UTC, Era Scarecrow wrote:
>  Now I just need to stress test it against some really large input and check for failures. Regardless it has a compression and decompression functions, along with benchmarking it vs the compression algorithm I'm trying to beat.

With 1 Million iterations:

new_compress: TickDuration(311404604)
id_compress   TickDuration(385806589)

 Approx 20% increase in speed (if i'm reading and did this right).

 I won't take this as the final verdict, but it is promising at least... Need a larger test sample to benchmark both functions against.

 Sample data is "E.s!(E.s!(E.s!(E.s!(E.s!(int).s(int).Result).s(E.s!(int)." etc from the bug listing: https://issues.dlang.org/show_bug.cgi?id=15831#c4

On 5/21/2016 11:26 PM, Era Scarecrow wrote:
> On Sunday, 22 May 2016 at 04:35:15 UTC, Era Scarecrow wrote:
>>  Now I just need to stress test it against some really large input and check
>> for failures. Regardless it has a compression and decompression functions,
>> along with benchmarking it vs the compression algorithm I'm trying to beat.
>
> With 1 Million iterations:
>
> new_compress: TickDuration(311404604)
> id_compress   TickDuration(385806589)
>
>  Approx 20% increase in speed (if i'm reading and did this right).
>
>  I won't take this as the final verdict, but it is promising at least... Need a
> larger test sample to benchmark both functions against.

It is promising. Need more!

On 5/22/2016 1:50 AM, Walter Bright wrote:
> It is promising. Need more!

I did figure out an improvement to the existing algorithm whereby it could skip forward by the length of the existing match rather than test every character (when it's looking for a longer match). But I have no clue how much of a speedup that would be.