[mercury-users] file compression in Mercury

[Ralph Becket]

> | I did indeed - I've got a fast, efficient implementation of LZW
> | compression as taken from the 129.compress SPEC95 benchmark.  It
> | runs at about half the speed of the C version.  
> 
> What about memory consumption? 
> Is your program able to compress, let's say, more than 100 Meg files?

The program runs in constant space: LZW scans the input stream looking
for substrings that it hasn't seen before.  When it detects a new
substring it assigns it a new code and sets up a substring -> code
mapping in a hash table.  The output stream is a stream of compression
codes.  When the hash table reaches 95% occupancy, no new codes are
allocated.  The compression process is started anew, after this point,
once the compression ratio falls by some amount.

> The reason why I ask is that I try to (re)-convince someone 
> that declarative
> programming "in the large" is viable. He told me he has lost 
> his faith in
> such languages a few years ago when he failed to implement an 
> efficient (both
> in terms of speed and memory consumption) functional program 
> that compresses
> more than 100 Meg files.

I'm pretty sure I tested this code on data files larger than that.  My
goals for conducting the experiment were
(a) to win a similar bet for an evening of beer from a friend who issued
a similar challenge;
(b) to find out whether a perspicuous Mercury implementation could be 
gracefully transformed into an highly optimised one;
(c) to get a paper out of it all (nearly done...) and
(d) to find out what optimisations are missing from the compiler and how
hard it is to work out when the optimisations it does perform will be
applied.

> | I think the decompression program has drifted slightly out 
> sync with the
> | compressor so I'll take a look and submit it (well, as soon as
> | MSR's lawyers get back to me about licenses etc. - hopefully
> | there won't be a problem).

This should be sorted out very soon.

Ralph
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------