[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: bit.lshift and performance - luabitop v.s. lua-5.2.0-work4
- From: KHMan <keinhong@...>
- Date: Thu, 14 Oct 2010 22:46:04 +0800
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 . 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
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.
Kein-Hong Man (esq.)
Kuala Lumpur, Malaysia