www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - [Rosettacode] Growable slices

reply "bearophile" <bearophileHUGS lycos.com> writes:
This task asks for an basic implementation of the the 
Lempel-Ziv-Welch (LZW) compression/decompression algorithm. I am 
keeping two D versions, the first one is minimal, and the second 
is a little more optimized:
http://rosettacode.org/wiki/LZW_compression#More_Refined_Version

There are of course ways to implement a really efficient ZLW 
compressor in D, and such implementation could be added as third 
D entry if it manages to be not too much long, but for the first 
two versions keeping the code very short is more important.

Despite the compressor in the second D entry is still not 
efficient at all, I have tried to make it not terrible regarding 
its efficiency, so I have defined a new kind of slice that can be 
extended, unlike the D slices, to avoid the string appends 
visible in the first D entry:


struct Slice {
     size_t start, end;
      property opSlice() const pure nothrow  safe  nogc {
         return original[start .. end];
     }
     alias opSlice this;
}

Slice w;
Tcomp[] result;
foreach (immutable i; 0 .. original.length) {
     auto wc = Slice(w.start, w.end + 1); // Extend slice.
     if (wc in dict) {
         w = wc;
     } else {
         result ~= dict[w];
         assert(dict.length < Tcomp.max); // Overflow guard.
         dict[wc] = cast(Tcomp)dict.length;
         w = Slice(i, i + 1);
     }
}


Is this showing a limit (problem) of D slices, or is this design 
better written in other ways?

Bye,
bearophile
May 15 2014
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 15 May 2014 at 09:00:13 UTC, bearophile wrote:
 This task asks for an basic implementation of the the 
 Lempel-Ziv-Welch (LZW) compression/decompression algorithm. I 
 am keeping two D versions, the first one is minimal, and the 
 second is a little more optimized:
 http://rosettacode.org/wiki/LZW_compression#More_Refined_Version

 There are of course ways to implement a really efficient ZLW 
 compressor in D, and such implementation could be added as 
 third D entry if it manages to be not too much long, but for 
 the first two versions keeping the code very short is more 
 important.

 Despite the compressor in the second D entry is still not 
 efficient at all, I have tried to make it not terrible 
 regarding its efficiency, so I have defined a new kind of slice 
 that can be extended, unlike the D slices, to avoid the string 
 appends visible in the first D entry:


 struct Slice {
     size_t start, end;
      property opSlice() const pure nothrow  safe  nogc {
         return original[start .. end];
     }
     alias opSlice this;
 }

 Slice w;
 Tcomp[] result;
 foreach (immutable i; 0 .. original.length) {
     auto wc = Slice(w.start, w.end + 1); // Extend slice.
     if (wc in dict) {
         w = wc;
     } else {
         result ~= dict[w];
         assert(dict.length < Tcomp.max); // Overflow guard.
         dict[wc] = cast(Tcomp)dict.length;
         w = Slice(i, i + 1);
     }
 }


 Is this showing a limit (problem) of D slices, or is this 
 design better written in other ways?

 Bye,
 bearophile
I don't think it shows a limit of "slices" in and out of itself, but rather the whole "range" concept, that conveniently encapsulates a start/end iteration scheme. The problem though is that, unlike iterators, these can only shrink, and never grow. Furthermore, it is usally hard to "split" a range into two parts, given a center iterator (especially for bidirectional-only ranges: EG: linked list). I think ranges/slices still provide more functionality and are worth it, but they do sacrifice *some* power: Growth and splitting. To be honest, what you are doing is essentially working with iterator pairs, disguised as indexes inside a "Slice" struct. Not that there's anything wrong with that, but that's my impression when looking at the code. Related: http://forum.dlang.org/thread/bhssgxfcscfbionhqcmn forum.dlang.org#post-umxlhsfqmfjwydemfdeb:40forum.dlang.org http://forum.dlang.org/thread/gpsiwnslxtsyfolymesc forum.dlang.org#post-mailman.2149.1353648522.5162.digitalmars-d:40puremagic.com
May 15 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
 There are of course ways to implement a really efficient ZLW 
 compressor in D, and such implementation could be added as 
 third D entry if it manages to be not too much long,
Third version added: http://rosettacode.org/wiki/LZW_compression#More_Efficient_Version I have tried to make it idiomatic D, but some of the C style is probably still present. The D code currently still requires five casts, and I have guarded them with asserts, like: assert(tmp >> oBits <= ubyte.max); result[outLen] = cast(ubyte)(tmp >> oBits); Perhaps with some more semantic knowledge of the program it's possible to avoid one or two of those casts. The D code contains a little less "type insanity" than the original C version :-) Bye, bearophile
May 16 2014
parent reply Artur Skawina via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
On 05/16/14 11:47, bearophile via Digitalmars-d-learn wrote:
 There are of course ways to implement a really efficient ZLW compressor in D,
and such implementation could be added as third D entry if it manages to be not
too much long,
Third version added: http://rosettacode.org/wiki/LZW_compression#More_Efficient_Version I have tried to make it idiomatic D, but some of the C style is probably still present.
Ugh. So how does it perform wrt the D version that I wrote for you last time? [1] [1] http://forum.dlang.org/post/mailman.2132.1353592965.5162.digitalmars-d puremagic.com) artur
May 16 2014
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Artur Skawina:

 So how does it perform wrt the D version that I wrote for
 you last time? [1]

 [1] 
 http://forum.dlang.org/post/mailman.2132.1353592965.5162.digitalmars-d puremagic.com)
From your answer:
First, the code above is practically a textbook example on how 
/not/ to
write readable and efficient code. So lets do a saner implementation:< I think the code I wrote is sufficiently readable, and surely efficiency was not its purpose. And November 2012 is lot of time ago, I have forgotten that answer of yours, sorry :-) I'll take a better look at it later today and I'll see if it's useful. Thank you. Bye, bearophile
May 16 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Artur Skawina:

 Ugh. So how does it perform wrt the D version that I wrote for
 you last time? [1]
I have done a benchmark with the various version (the first 3 are the ones on the Rosettacode site, and the #4 is yours): lzw1: 0.39 lzw2: 0.17 lzw3: 0.21 lzw4: 0.17 I think your comment was about an older version of the first entry, that is non meant to be fast, just short and simple. I think the second version is enough. Do you agree? The third version should be more efficient but for such small files it's slower than the second. Bye, bearophile
May 16 2014
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Friday, 16 May 2014 at 15:20:04 UTC, bearophile wrote:
 Artur Skawina:

 Ugh. So how does it perform wrt the D version that I wrote for
 you last time? [1]
I have done a benchmark with the various version (the first 3 are the ones on the Rosettacode site, and the #4 is yours): lzw1: 0.39 lzw2: 0.17 lzw3: 0.21 lzw4: 0.17 I think your comment was about an older version of the first entry, that is non meant to be fast, just short and simple. I think the second version is enough. Do you agree? The third version should be more efficient but for such small files it's slower than the second. Bye, bearophile
Arguably, your code allocates a lot. To speed it up, arguably, you could store a global immutable string containing characters 0 to char.max + 1. This way, when you build your dictionary (each time you enter compress), you at least don't have to allocate the string, but rather, slice your global immutable. Ditto for the lines "w = [ch];", which allocates, you could instead do "w = gAllChars[ch .. ch + 1]". (or "dict[b] = [b]" etc...) Well, just a quick idea... I'll give it a shot (next week).
May 16 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:

 Arguably, your code allocates a lot.
What version (1-2-3) do you mean?
 I'll give it a shot (next week).
I think the LZW entries are OK :) So if you want to work on Rosettacode it's better to write an entry that is missing in D. Bye, bearophile
May 16 2014
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Friday, 16 May 2014 at 15:49:10 UTC, bearophile wrote:
 monarch_dodra:

 Arguably, your code allocates a lot.
What version (1-2-3) do you mean?
Any of the versions where you can see "[c]" or "[b]" where c/b is a char/byte
May 16 2014
prev sibling parent Artur Skawina via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
On 05/16/14 17:20, bearophile via Digitalmars-d-learn wrote:
 Artur Skawina:
 
 Ugh. So how does it perform wrt the D version that I wrote for
 you last time? [1]
I have done a benchmark with the various version (the first 3 are the ones on the Rosettacode site, and the #4 is yours): lzw1: 0.39 lzw2: 0.17 lzw3: 0.21 lzw4: 0.17 I think your comment was about an older version of the first entry, that is non meant to be fast, just short and simple.
While I don't remember the numbers, I did test w/ gdc back then and both of your versions (from that thread) performed very poorly in a micro benchmark - I wasn't exaggerating when I said /an order of magnitude/, there really was a ~10 times perf difference. I didn't read the current entries on that page, so that might no longer apply, if you've modified them since. My point is that this third version that you announced here as almost- idiomatic-D is not even close to that goal; it's more or less a direct translation from C, and not like anything that would be written from scratch in D, hence the "ugh". Your own numbers above suggest that not even the "more efficient" claim is true.
 I think the second version is enough. Do you agree?
I don't see the point of the third ("C-in-D") one, other than to show how a direct C to D translation would look like. If /I/ was looking for a D code sample, then OUT[] compress(OUT=int, R)(R original) { IDAA!(OUT, const typeof(cast()original.front)[]) dictionary; OUT[] result; size_t l = 1; while (original.length>=l) { if (original.takeExactly(l) in dictionary) { ++l; continue; } result ~= dictionary[original.takeExactly(l-1)]; dictionary[original.takeExactly(l)] = cast(OUT)dictionary.length; original.popFrontN(l-1); l = 1; } return original.empty ? result : (result ~ dictionary[original]); } would have been much more useful than any of the currently available examples... Your #1 is more readable and easier to understand for someone not familiar with D and ranges, but extremely inefficient and not something that anyone would like to use in real life. Many of the rosettacode entries are very misleading and unidiomatic, they give a very wrong picture of the language they're trying to show off. This is probably not specific to D, but true for most of the represented languages. artur
May 16 2014