Page 1 of 2 12 LastLast
Results 1 to 30 of 42

Thread: diz.py release

  1. #1
    Member
    Join Date
    Aug 2012
    Location
    California
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts

    diz.py release

    Hello everyone. I'm posting here finally to release a compressor I wrote called Diz (Dizzy). It's just a simple PPMC compressor. I figured the best way to really learn about PPM was to make a working program using it! As such, the code is written primarily for simplicity and ease of change, so new ideas can be quickly tried. Python was used because it supports these goals. Compressing text the length of a novel takes a few seconds, which is good enough to develop with.

    Being a Python program, all source is there for you to read and twiddle with.

    I usually use pypy to run diz.py instead of Python, because it's several times faster! To compress enwik8.txt, the command would be:

    pypy diz.py -t -p enwik8.txt

    which produces enwik8.diz and 'Copy of enwik8.txt', and verifies the contents by matching CRCs. The '-p' displays progress by percent, useful for the long run.


    Suggestions or tweaks are very welcome! For instance, I wish there was better way of estimating escapes than single line of code used to do PPMC's estimate, but less than the pages of code needed for PPMD/PPMZ's SEE. Or maybe there's a good way to blend/interpolate contexts?
    Attached Files Attached Files

  2. #2
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    diz ran out of memory compressing mozilla from the Silesia corpus (51 MB file) using win32 pypy v1.9. I will try more tests later. enwik8.diz is 26,545,256 after 2333 seconds on a 2.0 GHz T3200, 3 GB memory. Did not test decompression yet. Edit: decompression OK.
    Last edited by Matt Mahoney; 4th August 2012 at 21:46.

  3. #3
    Member
    Join Date
    Aug 2012
    Location
    California
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Matt Mahoney View Post
    diz ran out of memory compressing mozilla from the Silesia corpus (51 MB file)
    Thanks for the test!

    It always impresses me that despite the testing one does, the first people to use your code always find issues!


    The mozilla and sao files are exhausting memory because there are so many contexts generated. I was blissfully ignoring complications from fitting in memory figuring that if enwik8.txt compressed, other smaller files should as well.

    Simply lowering the order near the top of codec_ppm.py to three gets mozilla to compress but I'm not happy giving up that space performance. I'll need to think about a scheme to prune contexts to stay within memory. I had earlier been wondering if small, infrequently used contexts were even worth tracking. It may take a certain number of uses before a context can make better predictions than it's parent context.

    I'll think this over and try a few things.

  4. #4
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    I added diz to the large text benchmark. It is ranked 90'th. http://mattmahoney.net/dc/text.html
    I didn't get the exact memory usage because running pypy under consmeter doesn't give accurate numbers. It was about 1350 MB half way through decompressing enwik9 (6 hours).

    PPM compressors like ppmd prune or discard the context tree when out of memory. Pruning (-r1 option) is slower but gives better compression. These also get better compression by modeling the escape codes (like PPMZ), which to me makes more sense than using a fixed model like PPMC, although it's more complex. See http://mattmahoney.net/dc/dce.html#Section_422 You can also get better compression using SSE, a low order context to fine tune the probabilities like in http://mattmahoney.net/dc/dce.html#Section_433

    Bitwise arithmetic is simpler to write than bytewise and in theory is just as fast in spite of requiring 8 coding operations per byte instead of 1. A simple bytewise coder would require up to 256 steps to calculate cumulative probabilities, and the best you can do is get this down to 8 using counter trees instead of linear accumulation. In practice, linear accumulation can be faster on highly redundant data by putting the most frequent symbols first, and because in higher order PPM contexts the number of symbols is much smaller, often just 1. This is why ppmd and ppmonstr are faster on highly compressible data.

  5. #5
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,205
    Thanks
    187
    Thanked 955 Times in 493 Posts
    > pages of code needed for PPMD/PPMZ's SEE.

    Actually SEE in ppmd is relatively simple - 2-3 lines basically.
    Still, you can try looking at
    http://ctxmodel.net/files/PPMd/ppmd_Jr1_sh8.rar
    (and also papers in /PPMd)
    speed optimizations and Shkarin's coding style in original source
    can be confusing, I guess.

    Anyway, ppmd's main idea for escape estimation is not SEE, but
    "inheritance". The new symbol is added to contexts in such a way
    that overall probabilities of all symbols remain the same.
    ie. if the probability of 'A' with escape to lower order was
    O1.pEsc*O0.pA, then we have to set O1.pEsc to O1.pEsc*(1-O0.pA)
    and O1.pA to O1.pEsc*O0.pA.

    > Or maybe there's a good way to blend/interpolate contexts?

    Well, there's CTW - http://www.sps.ele.tue.nl/members/F....esearchCTW.htm
    and the whole logistic mixing idea.
    Or maybe http://encode.su/threads/541-Simple-...xt-mixing-demo

    P.S. It would be probably a good idea to use a rangecoder instead of bitwise arithmetic,
    see http://encode.su/threads/1153-Simple...angecoder-demo

  6. #6
    Member
    Join Date
    Aug 2012
    Location
    California
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Roger Flores View Post
    The mozilla and sao files are exhausting memory because there are so many contexts generated. I was blissfully ignoring complications from fitting in memory figuring that if enwik8.txt compressed, other smaller files should as well.
    OK, I've added context pruning to diz making this version 2. Reading around, and as pointed out by Matt, it's common for PPM designs. I'd just never heard of it anywhere other than here.

    diz now works on all silesia files. Compression for files other than mozilla and sao (like enwik are unaffected because they don't trigger the pruning.


    The following is only for those interested in reading about context pruning. Everyone here already knows all this, so this is more for those that haven't written a PPM compressor.

    Some data points. The pypy diz.py version can store about 7 million contexts before exhausting memory.

    mozilla:
    5820000 [256, 65536, 3106670, 3670965]
    ratios: 256, 47, 1.2

    mozilla, at the 5,820,000th byte, has 256 different order 1 contexts, 65536 order 2, 3106670 order 3, and 3670965 order 4. 90% of the contexts are used only once (the initial case)!

    sao is the only other file from silesia that also overflows the contexts:
    7150000 [256, 65536, 2725088, 4005984]
    ratios: 256, 41, 1.5

    Why doesn't enwik8, which is 14 times larger that sao, also overflow contexts?
    enwik8:
    99990000 [205, 18611, 249159, 1203649]
    ratios: 91, 13, 4.8

    Sao and mozilla overflow because they use every byte value in many many combinations whereas enwik8 quickly narrows it's usage of values. Enwik8 only needs 1,471,624 contexts.


    For context pruning, I tried various ways to calculate a threshold. In the end though, for cases causing the context overflow, 90% of the contexts have only one use (the initial one), and are never reused. Realizing this, the algorithm simply walks the contexts and keeps only those used more than once (in Python you can't delete items while walking a container), like so:

    threshold = 2
    new_models = {}
    for k, v in self.models.items():
    if v.total >= threshold:
    new_models[k] = v

    self.models = new_models

    For some large files, the code may decide that not enough contexts were pruned, raise the threshold by one to three, and then repeat. There's no fancy calculations for threshold. Just remove those contexts with only one use, and if that isn't enough, raise and repeat.
    Attached Files Attached Files

  7. #7
    Member
    Join Date
    Aug 2012
    Location
    California
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thanks for all the links. I've been spending a lot of time going through them. I've been trying to decide what to work on next. I want to work on space improvements, but speed improvements makes everything easier to work on, and both of you suggest I swap out my arithmetic coder. My home grown coder isn't state of the art?

    I'll gladly use any coder that encodes a range (low, high) and is faster. The encoder stopped being fun when my first message larger than a few hundred bytes smacked into underflow. I tried for a while to contain underflow to only the encoding side. The encoder can't know if the range is going to converge low or high, because the future hasn't been modeled yet. The decoder can't model future symbols either, but the converged result is already provided by the encoder. Just use that instead of tracking underflow bits, but I couldn't make it work.

    >Bitwise arithmetic is simpler to write than bytewise and in theory is just as fast

    My ranges are written out bit by bit as the top bits converge, but because the range is greater than one bit I think you refer to it as bytewise. I read through http://mattmahoney.net/dc/dce.html#Section_32. I'm not sure how to adapt my range from the context model to a single bit. I get the sense that the paq series models and codes bitwise. I can see how this would model fine details and thus predict better, especially for binaries. But, thinking bitwise doesn't help me think and reason about text messages while I'm still learning about compression.


    >see http://encode.su/threads/1153-Simple...angecoder-demo

    I finally noticed, after the third reading, that past the code there's a whole long thread! I'll need to figure out which one ends up the best and try it. I just need to pass in a value, low and high, which I assume is standard.

  8. #8
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    I updated the Silesia benchmark. Still verifying decompression.
    http://mattmahoney.net/dc/silesia.html

  9. #9
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    After looking at arithmetic32.py I realized you already have written a bitwise coder. By bitwise I mean that it encodes or decodes one bit at a time, given a probability that the bit is a 0 or 1. The difference between this coder and PAQ or ZPAQ is that yours reads or writes 1 bit of compressed data at a time instead of 1 byte. To write 1 byte, check that the top 8 bits are the same, then write it and shift out 8 bits. Then you shouldn't need the read_bit() and write_bit() functions.

    Underflow should not be a problem. You always have low < high because otherwise you can normalize (write and shift out 32 bits). You start with low=0, high=0xffffffff and imagine that they continue this way, so the range is always at least 2. When you compute where to split the range, round down and add 1 if the upper part is selected.

    By "bytewise" I meant like in PPMd where the encoder and decoder receives input as an array of probabilities for each possible symbol and the range is divided up accordingly. If the encoder can't make each segment at least 1, then it discards part of the range so that it can normalize and make the range bigger.

    Older 16-bit encoders used a carry counter to deal with the range straddling a boundary. The idea was to extend low with a prefix of 01111... and high with 10000... and the counter gave the length of the prefix. This should not be necessary with 32 bit arithmetic because the compression loss due to rounding is insignificant. ZPAQ uses 16 bits of precision for probabilities (12 bits in PAQ), which would be a problem with a 16 bit range but is plenty for 32 bit.

  10. #10
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,205
    Thanks
    187
    Thanked 955 Times in 493 Posts
    > I'll gladly use any coder that encodes a range (low, high) and is faster.

    Its a little hard to predict how various coder optimizations would work with python.
    But at least getting rid of bit i/o should help either way.
    Also how about block i/o instead of reading and "unpacking" single bytes every time?
    Like, read a block of data and "unpack" it all at once, then feed to the coder?
    Btw, is there something similar to coroutines in python? It'd be convenient for this.

    Note that a bytewise order0 coder (aridemo-like) reaches about 60MB/s, and
    the speed of the "modern" bitwise coders is about 25MB/s (but these provide better compression).
    Bytewise/bitwise here applies to the probability estimation part only.

    > I tried for a while to contain underflow to only the encoding side.

    Underflow is not an issue when you work with {low;range} instead of {low;high} -
    the "low" can be simply shifted anytime if the range is small enough.
    And even overflow can be handled on the encoding side - the decoder can
    look like this:
    Code:
     uint GetFreq( uint totFreq ) { return code/(range/=totFreq); }
     void Decode( uint cumFreq, uint freq, uint totFreq ) {
       code  -= cumFreq * range;
       range *= freq;
       while( range<TOP ) (code<<=8)+=InpSrcByte(), range<<=8;
     }
    But some people prefer a "carryless" approach, where overflow is
    avoided by cutting down the range, in which case both encoder and
    decoder look kinda like this:
    Code:
     void Decode (uint cumFreq, uint freq, uint totFreq) {
        low  += cumFreq*range;
        range*= freq;
        while ((low ^ low+range)<TOP || range<BOT && ((range= -low & BOT-1),1))
           code = (code<<8) | InpSrcByte(), range<<=8, low<<=8;
     }
    Its simpler overall, but adds redundancy (especially in bytewise form)
    and slows down the decoding... in fact, maybe everything, because
    many optimizations are not applicable to carryless coders.

    > My ranges are written out bit by bit as the top bits converge,

    Yeah, so when you have variables with enough precision
    (ie not a 16-bit platform), you can wait for top _bytes_
    to converge, and then completely discard the whole bit i/o.

    Though then again, the whole idea of converging interval bounds
    is wrong and doesn't matter here - the high bytes of low/high
    may stay different forever, but who cares, when we're working
    with low/range.

    > But, thinking bitwise doesn't help me think and reason about text
    > messages while I'm still learning about compression.

    There's actually no difference. If you're not using a static distribution
    with lookup tables for decoding, it means there'd be binary flags somewhere -
    so the only choice is whether you search first, then update the coder,
    or do the search/update at once. Overall, the latter is simpler and provides
    better compression, and has other benefits, so...

    > I'll need to figure out which one ends up the best and try it.
    > I just need to pass in a value, low and high, which I assume is
    > standard.

    Then, I'd suggest to look at sh_v1 from http://compression.ru/sh/coders6c2.rar

    > The pypy diz.py version can store about 7 million contexts before exhausting memory.

    That's too few. Is it maybe possible to setup a huge array of integer values instead?
    Like that it could be possible to simulate low-level memory access.

    > For context pruning, I tried various ways to calculate a threshold.

    There's an alternative method btw - rebuilding the tree from scratch.
    Eg. you process a file from position 0 to 1M, then the dictionary overflows,
    so you discard it, and rebuild from 64k..1M window, then continue.

  11. #11
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    Silesia decompression verifies OK, but decompression is about 3 times slower than compression. I didn't time it but you can tell from the file creation times for all but the first:

    Code:
    10:24 AM         2,549,896 dickens.diz
    11:22 AM        19,002,190 mozilla.diz
    11:26 AM         2,447,581 mr.diz
    11:31 AM         2,889,153 nci.diz
    11:37 AM         2,873,535 ooffice.diz
    11:43 AM         2,865,373 osdb.diz
    11:45 AM         1,316,595 reymont.diz
    11:56 AM         5,526,140 samba.diz
    12:10 PM         5,234,494 sao.diz
    12:21 PM         8,163,835 webster.diz
    12:30 PM         4,280,582 x-ray.diz
    12:31 PM           717,110 xml.diz
      12 File(s)     57,866,484 bytes
    
    12:41 PM        10,192,446 dickens
    03:41 PM        51,220,480 mozilla
    03:56 PM         9,970,564 mr
    04:03 PM        33,553,445 nci
    04:26 PM         6,152,192 ooffice
    04:53 PM        10,085,684 osdb
    04:56 PM         6,627,202 reymont
    05:19 PM        21,606,400 samba
    06:19 PM         7,251,944 sao
    06:32 PM        41,458,703 webster
    07:20 PM         8,474,240 x-ray
    07:22 PM         5,345,280 xml
      12 File(s)    211,938,580 bytes
    Edit: results for ppmd -m256 (order 4). 56.3 sec. to compress, 63.7 sec. to decompress. The largest memory usage was 135 MB for mozilla.

    Code:
     2,497,415 dickens.pmd
    16,922,592 mozilla.pmd
     2,314,596 mr.pmd
     2,798,294 nci.pmd
     2,605,215 ooffice.pmd
     2,397,297 osdb.pmd
     1,262,148 reymont.pmd
     4,591,587 samba.pmd
     4,727,120 sao.pmd
     7,670,293 webster.pmd
     3,830,385 x-ray.pmd
       604,968 xml.pmd
     52,221,910 bytes
    Last edited by Matt Mahoney; 13th August 2012 at 21:31.

  12. #12
    Member
    Join Date
    Aug 2012
    Location
    California
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Matt Mahoney View Post
    Silesia decompression verifies OK, but decompression is about 3 times slower than compression. I didn't time it but you can tell from the file creation times for all but the first:

    Edit: results for ppmd -m256 (order 4). 56.3 sec. to compress, 63.7 sec. to decompress. The largest memory usage was 135 MB for mozilla.

    I have been timing them and noticed the difference. The compression and decompression times should be essentially the same, since the work to do, and the code, are essentially the same. The pypy JIT speeds up the python code by about 6x, but sometimes it doesn't on decompression. So sometimes decompression is about the same speed as encoding, and sometimes it's much slower. Running diz with Python always results in similar times for both operations.

    I've also noticed that C based encoders like ppmx are about 60x faster then when the pypy JIT is working right. Some of that is the memory use and gc. Some is from using the generic hashing instead of a tuned one. I could probably specialize for contexts with only one use. I'm probably not writing good Python here and there. My arithmetic coder may simply be outclassed.


    My plan is to improve the code a bit, and then see if the pypy team will be interested in finding why the JIT sometimes is 6x faster than Python and sometimes isn't, for the same code. After that, perhaps they might want to narrow the gap with C versions as well. The code is still small and simple that there aren't many places to look for problems. A 6x JIT speed up is quite good. On the other hand, knowing there's a further 60x of potential improvement means there could be some obvious, easy to find improvements.

  13. #13
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    What's the point in developing low-level algorithms using duck-typed languages? I think PyPy or whatever VM for duck-typed languages will be inferior to VMs or static compilation for statically typed languages for a long time.

    You can get equally succinct code with statically typed langugaes with heavy type inference, like Haskell or Scala.

    Edit:
    If that sounded rude, then I'm sorry. I didn't mean to offend anyone, I just wanted to point that duck-typed languages and high-performance low-level arithmetic algorihtms are (in some way) incompatible.
    Last edited by Piotr Tarsa; 14th August 2012 at 14:47.

  14. #14
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,205
    Thanks
    187
    Thanked 955 Times in 493 Posts
    > What's the point in developing low-level algorithms using duck-typed languages?

    1. I think its better than not developing low-level algorithms at all,
    because its more important to use a fashionable language.

    2. Its good to have actual code which can be compared with C/C++ compressors.
    Theoretical points don't convince anyone, while here we can compare real
    performance, memory usage, code size, readability etc.
    Actually it would be nice to have some examples for java/C#/javascript too.

    3. "see if the pypy team will be interested in finding why the JIT sometimes is 6x faster"
    That's one practical purpose, for example.

  15. #15
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    Isn't Python a fashional language? I didn't mean fashional BTW, only I've made a distinction between duck-typed languages and equally succinct statically typed ones.

    I've made a Java compressor - jTarsaLZP - which I posted on this forum. Coding efficient algorithms in Java is generally much more comfortable than in C/ C++ (thanks to very good devirtualization abilities of HotSpot) except the lack of unsigned primitives in Java which is a PITA.

    There are Java to JavaScript converters so it should be relatively easy to compile jTarsaLZP to JavaScript.

  16. #16
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,205
    Thanks
    187
    Thanked 955 Times in 493 Posts
    > I've made a distinction between duck-typed languages
    > and equally succinct statically typed ones.

    If you still think that python is "equally succinct", please look
    at the diz source here. The source size is the same as ppmd_sh,
    while the latter is _much_ more complicated.

    > I've made a Java compressor - jTarsaLZP - which I posted on this forum.

    Yeah. Entropy coding there seems pretty advanced actually, but
    the design choices make it hard to compare with anything.
    Can you make a simple console version and suggest another compressor(s)
    to compare it to?
    In fact I've got this when I tried to compress book1 with it:

    Code:
    >java -jar jTarsaLZP.jar
    
    Exception in thread "AWT-EventQueue-0" java.lang.OutOfMemoryError: Java heap space
            at tarsalzp.core.Common.<init>(Common.java:133)
            at tarsalzp.core.Encoder.<init>(Encoder.java:18)
    ...
    > Coding efficient algorithms in Java is generally much more
    > comfortable than in C/C++

    It really doesn't seem so though, not with your sources as example anyway.
    For one, in C++ I don't need to inline rangecoding manually, because there're templates.
    Basically, your code looks like C without macros.
    Comparing to that, C++ is certainly more comfortable.

  17. #17
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    When talking about comfort, I wasn't talking about that program (jTarsaLZP) in particular. jTarsaLZP was meant as a direct port of TarsaLZP and that was enough for experiments. Experiments which quickly ended, because multiple LZP models haven't worked well, at least for me.

    Writing a JavaScript version is a good idea, especially with Typed Arrays from recent ECMAScript incarnations. A console Java version is a good idea too.

    If you want to run jTarsaLZP you need to either increase the heap size to some ridiculous amount (I had to set it to few GiBs on my machine) or reduce slightly the value of variables lzpLevel4 and lzpLevel8 in file Common.java and then recompile, ie just do 'Clean and Build' under NetBeans. I have to admit that the GUI of jTarsaLZP is somewhat irritating.

    Edit:
    Probably NetBeans isn't needed, only Ant which uses the build.xml script. I'll check that.
    Last edited by Piotr Tarsa; 14th August 2012 at 17:21.

  18. #18
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,205
    Thanks
    187
    Thanked 955 Times in 493 Posts
    Imho it would be more interesting if you could write a PPM. Or a bitwise CM (to compare vs ccm/m1/etc).
    Or even a BWT postcoder.

  19. #19
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    I've uploaded a modified version which should use less memory and which has corrected lib folders so it doesn't need NetBeans to build, only Ant is needed.
    Attached Files Attached Files

  20. #20
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    Python doesn't look like a good choice for fast code. Maybe Fortran?
    http://shootout.alioth.debian.org/u3...re-fastest.php

  21. #21
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,205
    Thanks
    187
    Thanked 955 Times in 493 Posts
    intel fortran uses the same backend as intel C++.

  22. #22
    Member
    Join Date
    Aug 2008
    Location
    Planet Earth
    Posts
    776
    Thanks
    63
    Thanked 270 Times in 190 Posts
    For if you want to compare .NET speed http://www.codeproject.com/Articles/...-Csharp-vs-NET

  23. #23
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by Matt Mahoney View Post
    Python doesn't look like a good choice for fast code. Maybe Fortran?
    http://shootout.alioth.debian.org/u3...re-fastest.php
    As usually, it depends. You made a hugely generic statement that's true for some classes of problems but isn't for others.
    Want the fastest? Use asm. But almost always it's not worth it because you want the code to be fast enough for your goals, not as fast as possible. Even if the goal is being the world's fastest, for quite a few problems Python can be a good language to achieve it.
    Python is a valid choice for many fast codes because it lets you reach your goals with very high productivity. I remember one of Python patrons saying that his Python programs are usually faster than C ones - because productivity gains let him tweak the algorithm better. There's a difference on whether you write application logic or a library. In general, libraries are what does heavy lifting and performance loss from using a slow language for logic is negligible, yet efficient use of libraries is as important as libraries themselves. Also, more and more programs are not limited by CPU but I/O, so here you can too trade CPU efficiency for productivity and productivity for algorithmic efficiency and get a faster program overall.
    Compression? It's certainly library-type code even when packaged with GUI and is almost always CPU bound. I don't think that Python can be competitive with C(++) here in terms of efficiency/effort for a person who knows both languages equally well. And while I do Python for the living, my compression and related code is in C++. I view diz as a toy. If it gives the author fun, nothing more is needed.

    Quote Originally Posted by Shelwien View Post
    > I've made a distinction between duck-typed languages
    > and equally succinct statically typed ones.

    If you still think that python is "equally succinct", please look
    at the diz source here. The source size is the same as ppmd_sh,
    while the latter is _much_ more complicated.
    Made them equally readable and then we can talk. Your code style is highly compressed (1-letter variables, few comments, many statements per line), but reading it is very hard. That's not the case with diz.

  24. #24
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,205
    Thanks
    187
    Thanked 955 Times in 493 Posts
    > true for some classes of problems but isn't for others.

    I'd say its about _scale_ of problems, not class.
    If you have to work with 1000s of units, any script language would do.
    But when there're millions or billions of units, things suddenly become very different.
    There's a range where its impossible to solve a problem using plain python/java
    (without DBs, clusters etc) but for lower-level languages its still ok.
    Compression is just one example of that.

    > Want the fastest? Use asm. But almost always it's not worth it
    > because you want the code to be fast enough for your goals, not as
    > fast as possible.

    Yes, and in a sense, C++ is asm these days. There're intrinsics and inline asm,
    and some control over code generation.
    Plain asm these days is slower, because there're no code generation tools comparable
    to C/C++ compilers.

    > Even if the goal is being the world's fastest, for quite a few
    > problems Python can be a good language to achieve it.

    I'd appreciate some specific examples.
    I'd agree if you said that about haskell, or javascript even, but
    I can't recall any tasks where python is especially good.

    > There's a difference on whether you write application logic or a library.

    Its just an opinion, but to me this "application logic" is not programming at all,
    its scripting, and any non-trivial or large-scale step becomes a library call.
    So a developer doesn't have to care about platform specifics or efficient
    algorithms and data structures - its more of linguistics than programming.
    Actually I don't have anything against that though, its just not my job.

    > Python is a valid choice for many fast codes because it lets you
    > reach your goals with very high productivity.

    Yeah, right. Its especially impressive how they keep talking
    about high performance of scripts which do actual computing
    work via opencl. I mean, having an integrated C compiler
    hardly makes python faster, or does it?..

    > I remember one of Python patrons saying that his Python programs are
    > usually faster than C ones - because productivity gains let him
    > tweak the algorithm better.

    Its a bad example imho. Surely the maker of a tool would do better
    with that tool than without it.

    > In general, libraries are what does heavy lifting and performance
    > loss from using a slow language for logic is negligible, yet
    > efficient use of libraries is as important as libraries themselves.

    Yeah, to me its always fun how after reaching some scale people
    start piling up hardware, optimizing configs, using hacks, writing
    php compilers - just to continue using these libraries.

    Surely it requires a lot of creativity too, but its not like
    there're perfect libraries for everything, and solving actual
    problems is imho more important than finding tricks to keep
    "fast prototypes" working.

    > Also, more and more programs are not limited by CPU but I/O,
    > so here you can too trade CPU efficiency for productivity and
    > productivity for algorithmic efficiency and get a faster program overall.

    How would you write a python program that applies xor 0x55 to each byte of a file?
    Would it be possible to use async i/o?

    > Compression? It's certainly library-type code even when packaged
    > with GUI and is almost always CPU bound.

    Afaik its almost always bound by RAM speed.
    Except for LZs with a 32k window anyway.

    >> If you still think that python is "equally succinct", please look
    >> at the diz source here. The source size is the same as ppmd_sh,
    >> while the latter is _much_ more complicated.

    > Made them equally readable and then we can talk. Your code style is
    > highly compressed (1-letter variables, few comments, many statements
    > per line), but reading it is very hard. That's not the case with diz.

    1. I don't think that replacing all variable names in diz with one-letter ones
    would significantly change the picture.
    An example:
    Code:
    // python:
            v = in_file.read(1)
            if len(v) > 0:
                read_buffer = struct.unpack("<B", v)[0]
            else:
                read_buffer = 0
    
    // C:
            read_buffer = getc(in_file);
    2. My style is my style, and its still better than coding style of original ppmd,
    or lzma, or zlib, or basically any other format library.
    To me, the long variable names and redundant comments is what's annoying,
    because I want to see the program logic, and its easier when a function
    fits to one screen, instead of 10.

    Also in fact comparing to my usual code, ppmd_sh is relatively verbose:
    Code:
    PPM_CONTEXT* ProcessByte( Rangecoder& rc, int& c ) {
      PPM_CONTEXT* MinContext = MaxContext;
      if( MinContext->NumStats ) {
        processSymbol1<DECODE>(   rc, MinContext[0], c );
      } else {
        processBinSymbol<DECODE>( rc, MinContext[0], c );
      }
      while( !FoundState ) {
        do {
          OrderFall++;
          MinContext = MinContext->suff();
        } while( MinContext->NumStats==NumMasked );
        processSymbol2<DECODE>( rc, MinContext[0], c );
      }
      if( DECODE ) c = FoundState->Symbol;
      PPM_CONTEXT* p;
      if( (OrderFall!=0) || ((byte*)FoundState->getSucc()<UnitsStart) ) {
        p = UpdateModel( MinContext );
        if( p ) MaxContext = p;
      } else {
        p = MaxContext = FoundState->getSucc();
      }
      return p;
    }
    Most of variables and functions have relatively long names, so your
    complaint is a bit misplaced. Also the similar function in diz is
    called "push" and has about 4x more lines, so it'd be hardly helpful
    if I really made ppmd "equally readable".

  25. #25
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by Shelwien View Post
    > true for some classes of problems but isn't for others.

    I'd say its about _scale_ of problems, not class.
    If you have to work with 1000s of units, any script language would do.
    But when there're millions or billions of units, things suddenly become very different.
    There's a range where its impossible to solve a problem using plain python/java
    (without DBs, clusters etc) but for lower-level languages its still ok.
    Compression is just one example of that.
    Why w/out clusters? The problems that require them are exactly the ones that have the largest scale. They get increasingly important, they get to work with lots of objects and they are expensive => performance matters. Yet Hadoop is written in Java. And Tahoe-LAFS in Python. Both are designed to scale to arbitrary sizes.
    I think it's rather about a combination of 2 factors, large number of objects and small object size where they lose.

    Quote Originally Posted by Shelwien View Post
    Plain asm these days is slower, because there're no code generation tools comparable
    to C/C++ compilers.
    We've been hearing it for what, 20 years? Yet asm magicians keep showing time after time that they beat compilers. Example? I'm a bit into SHA3 competitors. Of 5 finalists, 3 come with ASM implementations, some with several of them (for different CPUs). The other 2 use intrinsics.

    Quote Originally Posted by Shelwien View Post
    > Even if the goal is being the world's fastest, for quite a few
    > problems Python can be a good language to achieve it.

    I'd appreciate some specific examples.
    I'd agree if you said that about haskell, or javascript even, but
    I can't recall any tasks where python is especially good.
    A distributed filesystem over a slow network, like Tahoe-LAFS over I2P. I think it's one of extreme cases of an I/O bound problem and here language performance is something that doesn't matter at all.
    Really, I don't know if Tahoe-LAFS works good because there's nothing to compare it to, but anyway Python's productivity would give it an edge. Maybe not over anything, because Haskell, Ruby, Scala, probabaly Erlang too could give you very comparable results, but IMHO Python is among top options.
    There's also a weird example of PyPy, which is itself written in Python, yet it beats all other (major?) implementations (CPython, Jython and IronPython).

    > There's a difference on whether you write application logic or a library.

    Its just an opinion, but to me this "application logic" is not programming at all,
    its scripting, and any non-trivial or large-scale step becomes a library call.
    So a developer doesn't have to care about platform specifics or efficient
    algorithms and data structures - its more of linguistics than programming.
    Actually I don't have anything against that though, its just not my job.
    Library calls to do most of job? Certainly. Platform specifics? Rarely matter. I agree here. Algorithms? Well, it's quite different, you still have to keep eye on complexity. Though indeed there are fewer interesting algorithms in use.

    > Python is a valid choice for many fast codes because it lets you
    > reach your goals with very high productivity.

    Yeah, right. Its especially impressive how they keep talking
    about high performance of scripts which do actual computing
    work via opencl. I mean, having an integrated C compiler
    hardly makes python faster, or does it?..
    I don't know what are you talking about, opencl didn't even cross my mind.

    > In general, libraries are what does heavy lifting and performance
    > loss from using a slow language for logic is negligible, yet
    > efficient use of libraries is as important as libraries themselves.

    Yeah, to me its always fun how after reaching some scale people
    start piling up hardware, optimizing configs, using hacks, writing
    php compilers - just to continue using these libraries.

    Surely it requires a lot of creativity too, but its not like
    there're perfect libraries for everything, and solving actual
    problems is imho more important than finding tricks to keep
    "fast prototypes" working.
    Such hacking is not what I meant. Yeah, it happens, but I find it low. I was talking tweaking your algos, so they use lower number of expensive calls rather than hacking the calls, so they execute faster.

    > Also, more and more programs are not limited by CPU but I/O,
    > so here you can too trade CPU efficiency for productivity and
    > productivity for algorithmic efficiency and get a faster program overall.

    How would you write a python program that applies xor 0x55 to each byte of a file?
    Would it be possible to use async i/o?
    Frankly - I don't know how would I do it. But it looks like a trivial example where solution in any language would be roughly equally complex. Async I/O is not a problem, you just have to use some library.

    > Compression? It's certainly library-type code even when packaged
    > with GUI and is almost always CPU bound.

    Afaik its almost always bound by RAM speed.
    Except for LZs with a 32k window anyway.
    True, that was a mental shortcut, but incorrect.

    >> If you still think that python is "equally succinct", please look
    >> at the diz source here. The source size is the same as ppmd_sh,
    >> while the latter is _much_ more complicated.

    > Made them equally readable and then we can talk. Your code style is
    > highly compressed (1-letter variables, few comments, many statements
    > per line), but reading it is very hard. That's not the case with diz.

    1. I don't think that replacing all variable names in diz with one-letter ones
    would significantly change the picture.
    An example:
    Code:
    // python:
            v = in_file.read(1)
            if len(v) > 0:
                read_buffer = struct.unpack("<B", v)[0]
            else:
                read_buffer = 0
    
    // C:
            read_buffer = getc(in_file);
    I would do it simply by
    Code:
    read_buffer = ord(in_file.read(1))
    and catch an exception later (which is about as much code as EOF checking in C), but maybe I miss something

    2. My style is my style, and its still better than coding style of original ppmd,
    or lzma, or zlib, or basically any other format library.
    Don't know about ppmd, but I don't agree about lzma and zlib.
    Both are quite bad, but IMHO better. bzlib and lzham are examples of more readable things. But diz beats them both in this regard.

    To me, its long variable names and redundant comments is what's annoying,
    because I want to see the program logic, and its easier when a function
    fits to one screen, instead of 10.
    Verbose names rarely increase number of lines. Comments do, but then they let you get some meaning of the code much quicker. Usually when I dig in a foreign code, I have to well understand 1-5% of what I read. The rest - only enough to know that's not what I'm looking for and sometimes - what's the next piece that I have to look up. In such cases both comments and verbose names speed things up.
    In the pieces that I'm trying to undestand they help too, having basic understanding makes a better start than none at all and normally it's well worth the extra screen space.

    Also in fact comparing to my usual code, ppmd_sh is relatively verbose:
    Code:
    PPM_CONTEXT* ProcessByte( Rangecoder& rc, int& c ) {
      PPM_CONTEXT* MinContext = MaxContext;
      if( MinContext->NumStats ) {
        processSymbol1<DECODE>(   rc, MinContext[0], c );
      } else {
        processBinSymbol<DECODE>( rc, MinContext[0], c );
      }
      while( !FoundState ) {
        do {
          OrderFall++;
          MinContext = MinContext->suff();
        } while( MinContext->NumStats==NumMasked );
        processSymbol2<DECODE>( rc, MinContext[0], c );
      }
      if( DECODE ) c = FoundState->Symbol;
      PPM_CONTEXT* p;
      if( (OrderFall!=0) || ((byte*)FoundState->getSucc()<UnitsStart) ) {
        p = UpdateModel( MinContext );
        if( p ) MaxContext = p;
      } else {
        p = MaxContext = FoundState->getSucc();
      }
      return p;
    }
    Most of variables and functions have relatively long names, so your
    complaint is a bit misplaced. Also the similar function in diz is
    called "push" and has about 4x more lines, so it'd be hardly helpful
    if I really made ppmd "equally readable".
    I acknowledge that it's better than some other of your code that I've seen, but there are still places with magic 1-character variables and constants.
    Code:
      void init( void ) {
        cs = 0xFF;
        x0 = x1 = 0;
        i  = 0;
        k  = 5;
      }
    
      int cache_byte( int c ) {
        int d = cs&0x80 ? -1 : byte(x1);
        (x1>>=8)|=(x0<<24);
        (x0>>=8)|=(c <<24);
        cs<<=1; i++;
        return d;
      }
    I'm tired, I should be sleeping for at least 2 hours already, but it took me like 5 minutes to get a rough understanding of these couple of lines and I still have no idea why cs is not a counter. I guess I'd have to look into surrounding code, but why do I have to? This knowledge is relevant for this piece of code, yet placed in some other, not clearly linked place. And k? I guess I'd have to (roughly) understand the entire module even if I needed just these 2 functions.
    OT: the code won't work on Linux AMD64, among others.

  26. #26
    Member
    Join Date
    Aug 2012
    Location
    California
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    I just wanted to point that duck-typed languages and high-performance low-level arithmetic algorihtms are (in some way) incompatible.

    I think what you're saying is that a typed language is necessary for acceptable performance. I think the latest thinking is exploring run time traces to drive JIT performance. The information on how the code is actually used drives code generation choices. It's not going to be better than a solid programmer coding, measuring, tuning, repeating, but it could be better than what most people write for the majority of their code. It could potentially be good enough for traditionally low-level only code:

    http://morepypy.blogspot.com/2011/07...in-python.html

    I think before long the people that hate types will show that they can generate equally good code. On the other hand, I think people trying to use type free code will still have the code die in surprising ways at inopportune moments because it was "misused".



    I'll explain why *I* wrote diz using Python, if that helps, because it's simple.

    I wrote diz using Python instead of C, for the same reason that I didn't use asm either - I want to minimize the time I spend writing code. With that savings, I can use it to improve the algorithms involved. It's the same reasoning for every language since assembly.

    If you still find the code is not fast enough, then you move the slow code into a C library and call that. If that's too slow you move the slow portion into assembly. The pypy team is moving the goal post a bit with their JIT. We'll see how well that works outs.

    This has worked out for diz because I had a lot to learn and figure out, so I'm writing and changing code more than normal.

    Diz is not about speed. It's about me learning how to make a real PPM that works. The fact that I've placed *on* Matt's chart is pretty cool news in this house! And hopefully I'll end up with a readable one, because most of the ones I've read through are impossible to understand. They seem like random collections of letters getting ++, >> and = 1 applied to them, without direction. It's unfortunate, because I really want to understand the ideas in the code.



    P.S., any lousy python code is my fault. The code has accumulated off and on over several years and varies a fair amount as I learn what works and what doesn't, especially for binary files. Code changes or "Are you serious?" questions are appreciated, since the code will improve.

    >read_buffer = struct.unpack("<B", v)[0]
    I suspect this came from modifying out_file.write(struct.pack("<B", write_buffer)) to read instead. Cleaned to use ord() now. Any better way to write a long as a byte?

  27. #27
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    Arrrgh. This lousy forum engine ate my entire post so I have to rephrase it.

    I wrote diz using Python instead of C, for the same reason that I didn't use asm either - I want to minimize the time I spend writing code. With that savings, I can use it to improve the algorithms involved. It's the same reasoning for every language since assembly.

    If you still find the code is not fast enough, then you move the slow code into a C library and call that. If that's too slow you move the slow portion into assembly. The pypy team is moving the goal post a bit with their JIT. We'll see how well that works outs.
    1. As I've said - there are statically typed languages where you can write as quickly as in Python or even faster. And static typing gives a lot of benefits, besides good performance there's static type checking for eg catching some bugs before testing the program or improved refactoring abilities. Certainly Python is often more comfortable than C, but it seems you're deliberately omitting succint statically-typed languages.
    2. Theoretically better algorithms, ie those that have lower asymptotic complexity, aren't always better in practice. In reality the opposite is often true. Badly optimizing JITs alters the perceived computational complexity, I wouldn't be surprised if algorithms that are way faster under Python are way slower in C, and vice versa.
    3. Using Python here to improve PyPy quality doesn't bring any direct advantage to data compression scene.
    4. Data compression is almost always about tuning parameters. Some people run optimization procedures for weeks using tools they wrote. If PyPy produces code that is tens times slower, then optimization phase would take years with Python.
    5. Automatic code optimization (ie either static or JIT) is hard and duck typing makes it even much harder. It's much easier to effectively JIT a small algorithm, but the hardness grows with the complexity and size of code. That's why PyPy shines in microbenchmarks but stop shining in anything more complicated.
    6. IIRC Twitter has moved from Ruby to Scala and they found Scala to be in the same productivity class, while being ten times faster or so.
    7. I bet Google is investing millions of dollars into its V8 Javascript engine, yet I didn't find it anywhere close to statically typed languages in terms of performance.

    Diz is not about speed. It's about me learning how to make a real PPM that works. The fact that I've placed *on* Matt's chart is pretty cool news in this house! And hopefully I'll end up with a readable one, because most of the ones I've read through are impossible to understand. They seem like random collections of letters getting ++, >> and = 1 applied to them, without direction. It's unfortunate, because I really want to understand the ideas in the code.
    I prefer papers to code, no matter how readable that code is. Final code contains all the details and optimizations in place, while papers usually introduce readers step by step into the problem.

    I'm not trying to force you to cease development in Python, I'm just saying that your statements are wrong. Duck typing doesn't bring any tangible advantage in heavy computation world, while it can be a great pain.
    Last edited by Piotr Tarsa; 15th August 2012 at 16:31.

  28. #28
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,205
    Thanks
    187
    Thanked 955 Times in 493 Posts
    @Roger Flores:

    > I wrote diz using Python instead of C, for the same reason that I
    > didn't use asm either - I want to minimize the time I spend writing code.

    I think if you really wanted to minimize coding, you could, well, not write that much?
    Especially things with 100s of existing implementations like crc and AC?
    Or things like commandline parsing and format version checking, which don't
    affect compression in any way?

    Let's compare diz with http://ctxmodel.net/files/green/green_v3a.rar :
    Code:
              bytes  LoC   csize   ctime dtime   order
    diz-2    50,529 1465  223698 10.890s 13.343s     4
    diz-2                 236696 70.250s            16
    green_3a  7,471  302  229747 10.297s 10.391s     4
    green_3a              214846 14.062s 14.094s    16
    tree 4   14,104  551  226615  2.000s  2.032s     4
    tree 16               214843  2.406s  2.438s    16
    Note that "green" recomputes the statistics dynamically all the time,
    by scanning the data - that's what I did when I wanted simple code.

    > With that savings, I can use it to improve the algorithms involved.

    But apparently you can't, because testing is slow, and it can't store
    all the necessary statistics?

    > It's the same reasoning for every language since assembly.

    Well, C is better than asm because it hides register allocation
    and provides more compact and structured syntax than assembly mnemonics.
    C++ is better than C because of namespaces, pattern matching
    (finding code by inferred types) and compile-time code generation.
    Then, some languages are based on specific engines, and thus are
    better for their specific domains.
    But how python fits into this picture (aside from fashion), I don't
    really understand. Can you suggest anything that is easy to do in python,
    and hard to do in C++?

    > If you still find the code is not fast enough, then you move the
    > slow code into a C library and call that.

    Well, that's the case with compression algorithms.

    > If that's too slow you move the slow portion into assembly.

    Not really. As I said, there're tools for/in C/C++ which don't
    exist for asm. Mostly code specialization based on constant parameters.
    So to design anything minimally complex using plain asm would
    require writing (or finding) similar tools for asm first, or
    C++ version would end up faster.

    > most of the ones I've read through are impossible to understand.

    More like you don't have patience to try and understand maybe?
    I agree that most of the sources are not very easy to read,
    but its still easier than decompiling executables, which I had
    to do a few times.

    > They seem like random collections of letters getting ++, >> and = 1
    > applied to them, without direction.

    People frequently call it "premature optimization", but the thing is,
    these kinds of algorithms don't work without compact data structures
    (there's not enough memory even with all optimizations), so we end
    up packing 4 symbols into an int, then accessing them via >> etc.

    > It's unfortunate, because I really want to understand the ideas in
    > the code.

    As I mentioned, there're a few papers in there - http://www.ctxmodel.net/files/PPMd/
    And you can ask on the forum.

  29. #29
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    Writing fast compression code is hard. I've been doing it for years and I still can't make the Pareto frontier on most of the benchmarks.

    Of course you are most productive in the language you know best. It just happens to be C++ for me. It's what most compression code is written in anyway, besides C and assembler. It's not just duck typing. C was designed to be fast and close to the hardware since the 1970's, and C++ was designed not to give up any of that speed. It's a complex language because it's so old, but that also means that there are decades of optimization work done on the compilers. If you look at the assembler output you'll see. For example, an expression like (a<<b | a>>32-b) compiles to a single x86 rotate instruction. (a/3) compiles to a multiply and shift because it's faster than division. Many loops are automatically vectorized using SSE2.

  30. #30
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,205
    Thanks
    187
    Thanked 955 Times in 493 Posts
    @Piotr Tarsa:

    > 3. Using Python here to improve PyPy quality doesn't bring any
    > direct advantage to data compression scene.

    Well, if a different language choice helped to improve compression somehow,
    I think it would be great either way.
    I don't really believe that its possible, because with all the modern languages
    the code becomes totally ugly when its necessary to work with bitfield structures,
    But in theory it can happen, and I think that a new python PPM is still better
    than no new attempts at all.

    Also its always good to have more alternatives for comparison.
    Benchmarks tell us that java and C# are not really slower than C++,
    so why don't we have more implementations?

    In fact, there're lots of points where its possible to improve the probability estimation,
    so having more people not concerned about processing speed is always good.

    Just that my impression, kinda confirmed by that contest
    is that new languages are too strict, so people have to avoid doing anything new,
    because making a new library and distributing it is too much work.

    > 4. Data compression is almost always about tuning parameters. Some
    > people run optimization procedures for weeks using tools they wrote.
    > If PyPy produces code that is tens times slower, then optimization
    > phase would take years with Python.

    Its kinda a bad example, considering that my optimizer is written in perl.

    > I prefer papers to code, no matter how readable that code is.

    I think it doesn't really work for compression.
    Papers end up with pseudocode like:
    http://en.wikipedia.org/wiki/Lempel%...coding_of_bits
    which is much harder to understand than corresponding C code,
    and frequently contains mistakes anyway, because it can't be tested.

    For example, most of ppmd's inheritance logic ended up very strange,
    because it had to be computed with byte counters and limited-precision integer arithmetics,
    so discussing it out of context doesn't make much sense.
    And in context we end up with C and/or asm, because its what cpu can do, and
    the syntax is compact and not ambiguous, unlike natural languages.

    > Duck typing doesn't bring any tangible advantage in heavy computation world

    Well, C++0x now has the "type" auto, so it does have some uses

    And seriously, lists and maps and such are very convenient to have.
    They just use too much memory to be helpful for compression.

Page 1 of 2 12 LastLast

Similar Threads

  1. packMP3 v1.0c release
    By packDEV in forum Data Compression
    Replies: 11
    Last Post: 11th October 2012, 17:48
  2. Wondering whether to release my deflate recompressor
    By m^2 in forum Data Compression
    Replies: 15
    Last Post: 4th November 2011, 19:31
  3. ZPAQ pre-release
    By Matt Mahoney in forum Data Compression
    Replies: 54
    Last Post: 23rd March 2009, 02:17
  4. FreeArc 0.40 pre-release version
    By Bulat Ziganshin in forum Forum Archive
    Replies: 110
    Last Post: 2nd January 2008, 23:29
  5. quad 1.07BETA2 - pre-release of 1.08 available
    By encode in forum Forum Archive
    Replies: 4
    Last Post: 11th March 2007, 22:59

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •