Efficient mutable byte array in native Lua

Question

I am trying to make an efficient implementation of an LZ77 decoder in native Lua (i.e. no C library, and no dependencies on non-core Lua libraries) - see liblzg.

For loading and parsing the binary file, a Lua string works perfectly, and with good performance (e.g. using the s:byte(k) method). However, for creating the decoded output data, strings are not very optimal, since they are immutable, and string concatenation tends to take lots and lots of time when the output becomes large.

The decoder must be able to:

• Append one byte to the output at a time (up to millions of times)
• Read (more or less random access) from the output buffer

What are the best options? The size of the output data is known before hand, so it can be pre-allocated.

Answer 1

Avoid string concatenation: save output strings to a table and write all strings in it at the end. If you're concerned about the table getting too big, flush it periodically. See http://www.lua.org/pil/11.6.html

Answer 2

Sounds like a perfect job for table.concat your output is just a table of bytes.

When you need to copy, you do it as you normally would for a table. eg:

for i=#output-5,9 do output[#output+1]=output[i] end

When you finally are done with the output stream, convert it to a string with str=table.concat(output)