base64 encoding in Lua par duex January 13, 2014 at 10:54 am

Sleep. Helps the brain. After getting a decent nights sleep, I considered the algorithm I used (which was considerably faster than anything I previously found) and figured it could be better after finding another version on github. Re-thinking my main conversion routine doubled the performance. Natural Lua code is still orders of magnitude slower than optimized and compiled “native” code, but these routines are “usably fast-enough” for the purposes I had in mind.

base64 (GNU 8.21) base64.lua (github/ErnieE5) base64.lua (github/paulmoore) Lua wiki
0.055s 0.555s 0.916s 2.586s

When I optimize code I like to figure out what is redundant. (A good optimizing C/C++ compiler can make you lazy at times.) Any optimization is about understanding the platform and usage. With natural Lua (i.e. Not LuaJit or a binary c library) there are a few main factors for optimization.

  • function calls
  • variables
  • branching

These optimizations apply to very tight loops. Most of the time, I prefer to have “lots” of functions and keep code as reusable as possible. (The functional programming aspects of Lua are very handy at times.)

Every function call is going to incur the  overhead of stack management. If the routine is fairly small, the overhead of the management code can add significant time to a routine. This applies for all programming languages, but with a “scripting” language that doesn’t have deep algorithmic analysis you need to keep this in mind. It adds up when millions of iterations call a method.

Variables in Lua are all reference counted. Tables and strings can have significant impact to runtime performance if a loop creates and discards these elements for each iteration. (One of the reasons table.concat is much better for large string assembly over using s=s..”more” in a loop.)

Branching can have significant performance implications on tight loops. A specific case of a branch that will slow Lua down (in comparison!) is the idea of ‘if not end then … else … end’. If the main loop of a routine has this type of logic for every iteration and the branch only fires the end routine at the very end, it very well could shave many cycles off the routine. If possible, have the loop end ~before~ the “special” condition and then handle the special condition at the end. (e.x. in base64 encoding all inputs are 3 bytes and the tail has special padding for inputs that are not evenly divisible by three)

The moral to this story? No matter HOW good you ~think~ you are, in most cases you can do better. (Also, no matter how much time you spend searching for something “in the cloud” you are going to miss something.)

Ernie

Comments are closed.