Re: bit.lshift and performance - luabitop v.s. lua-5.2.0-work4

[KHMan <keinhong@...>]

On 10/13/2010 10:34 AM, David Manura wrote:
> [snip snip snip]
> Another area of difficulty involves a function that reverses the order
> of bits [5].  There is not an easy way to optimize the pure Lua form
> with existing native bitwise operations:
>
>    local function msb(bits, nbits)
>      local res = 0
>      for i=1,nbits do
>        local b = bits % 2
>        bits = (bits - b) / 2
>        res = res * 2 + b
>      end
>      return res
>    end
>
> LuaBitOp does implement a function "bswap" that reverses the order of
> bytes, but that only would help partly (e.g. swap bytes with bswap and
> then swap bits in each byte via an 8-bit lookup table).

Okay, one more niggling item...

Do you have timing data on the relative cost of building the 
Huffman trees? Should check it before deciding on whether to 
optimize this. It is called up to only ~300 times for both tables 
and this is done once per block of max 64KB of data. In any case, 
this one is restricted to the lengths of the Huffman code, 1-15 
bits, as stated in the source code.

For example, in compressing a 111,261 byte text file (Calgary 
corpus, bib), on a version of LZF I get 19,443 LZ matches and 
11,501 bytes of literals. This compares to 2 blocks of <=64KB in 
gzip, or maybe ~650 calls of bi_reverse() in gzip. So it is 
important to check how long the Huffman trees are taking to build, 
or relative workloads of each portion of gzip.

--
Cheers,
Kein-Hong Man (esq.)
Kuala Lumpur, Malaysia