CODEWITHSUNDEEP
compressionlua
marcus256
marcus256

Reputation: 231

Efficient mutable byte array in native Lua

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:

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

Upvotes: 11

Views: 5014

Answers (2)

daurnimator
daurnimator

Reputation: 4311

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)

Upvotes: 9

lhf
lhf

Reputation: 72312

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

Upvotes: 10

Related Questions