Path: utzoo!utgpu!watserv1!watmath!att!rutgers!ucsd!swrinde!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!metro!natmlab.dap.csiro.au!ditsyda!evans
From: evans@ditsyda.oz (Bruce.Evans)
Newsgroups: comp.os.minix
Subject: Re: Compression programs: compress vs lharc vs comic
Keywords: Compr. rate: comic, Speed: compress
Message-ID: <2683@ditsyda.oz>
Date: 10 Jul 90 14:16:21 GMT
References: <1822@tuegate.tue.nl> <1815@ns-mx.uiowa.edu>
Organization: CSIRO DIT Sydney, Australia
Lines: 48

In article <1815@ns-mx.uiowa.edu> williams@umaxc.weeg.uiowa.edu.UUCP (Kent Williams) writes:
>
>Can the author summarize the algorithm used?  It looks as though too much
>time is spent in looking for stuff -- maybe hashing could be used for
>one or another step to speed things up.

Profiling the 16-bit version gave the following (for 18.8 sec to compress
comic.c):

  10.042   10042  53.31%  _memrchr  *******************************************
   4.801    4801  25.48%  _get2pai  *********************
   1.735    1735   9.21%  _getp1    *******
   0.524     524   2.78%  _cdsret   **
   0.238     238   1.26%  _eqlen    *
   ...
  18.093   18093  96.06%  TOTAL IN RANGE
   0.742     742   3.93%  OTHER
  18.835   18835 100.00%  TOTAL

That's with memrchr in assembler!  memrchr is used to find an anchor for a
string lookup. Hashing just on the first char would reduce this step
considerably. I don't know how expensive maintaining the hash table would be.

Here are some times for the compression programs available to me on a 20MHz
386. I/O times are significant for the faster programs (5 to 10 sec).
---
Times for packing the Minix dictionary (407564 bytes).

Program			compression	time	un-time	O/S	compiler
------------------------------------------------------------------------
pkzip1.10 -es		60%		   9	  6	DOS	?
pkpak3.61		59%		   9	  6	DOS	?
compress4.01 -b 13	57%		  14	 12	minix-3	gcc1.36
compress4.01 -b 16	58%		  15	 12	minix-3	gcc1.36
zoo2.01			59%		  20	 17	minix-3	gcc1.37
compress4.01 -b 13	57%		  27	 14	DOS	msc 4.0
compress-minix1.3	57%		  41	 23	minix	cc1.3
compress4.01 -b 13	57%		  45	 23	minix	bcc1.0
pkzip1.01		66%		  48	  6	DOS	?
pak2.10			67%		  52	  9	DOS	?
compress-??? -b 16	58%		  83	 43	DOS	?
lharc1.13c		67%		  89	 13	DOS	?
lharc1.00		67%		 168	 17	minix-3	gcc1.37
lharc1.00		67%		 275	 36	minix	bcc1.0
comic			67%		1504	 20	minix-3	gcc1.37
comic			67%		1782	 34	minix	bcc1.0
-- 
Bruce Evans		evans@ditsyda.syd.dit.csiro.au