+ Reply to Thread
Results 1 to 15 of 15

Thread: Found a very good Lua optimization article...

  1. #1
    Telaran
    Join Date
    Apr 2011
    Posts
    64

    Default Found a very good Lua optimization article...

    Found this little gem on the Internet... makes for some good reading.

    Article

    Explains how Lua handles variables, stores strings etc.

  2. #2
    RIFT Community Ambassador the_real_seebs's Avatar
    Join Date
    Jan 2011
    Posts
    16,859

    Default

    While this is cool, it is worth noting that Rift uses luajit, and thus may have different performance characteristics.
    You can play WoW in any MMO. You don't have to play WoW in RIFT. Oh, and no, RIFT is not a WoW clone. Not having fun any more? Learn to play, noob! I don't speak for Riftui, but I moderate stuff there. Just came back? Welcome back! Here's what's changed. (Updated for 2.5!)

  3. #3
    Plane Touched Verea's Avatar
    Join Date
    Feb 2011
    Location
    Netherlands
    Posts
    200

    Default

    Quote Originally Posted by the_real_seebs View Post
    While this is cool, it is worth noting that Rift uses luajit, and thus may have different performance characteristics.
    Wrong, LuaJIT is a compiler for Lua code, which is generally faster than the regular Lua compiler. These optimization characteristics discussed in that topic/book whatever it is, really applies to most languages.

    Very useful, though, I already read it.
    Verae, level 60 Cleric @ Blightweald, Guild Master of Tea Club
    I want to fly like an eagle, to the sea.
    I want to fly like an eagle, let my spirit carry me.

  4. #4
    RIFT Community Ambassador the_real_seebs's Avatar
    Join Date
    Jan 2011
    Posts
    16,859

    Default

    There's a lot of things which will apply across languages, but there are cases where JIT compilers may have different characteristics. I don't recall for sure, but I believe some of the internal representations differ between the classic Lua and luajit.
    You can play WoW in any MMO. You don't have to play WoW in RIFT. Oh, and no, RIFT is not a WoW clone. Not having fun any more? Learn to play, noob! I don't speak for Riftui, but I moderate stuff there. Just came back? Welcome back! Here's what's changed. (Updated for 2.5!)

  5. #5
    Plane Touched Verea's Avatar
    Join Date
    Feb 2011
    Location
    Netherlands
    Posts
    200

    Default

    Quote Originally Posted by the_real_seebs View Post
    There's a lot of things which will apply across languages, but there are cases where JIT compilers may have different characteristics. I don't recall for sure, but I believe some of the internal representations differ between the classic Lua and luajit.
    Very true, but the article linked doesn't discuss any of these things. The article even makes a friendly nod towards LuaJIT and suggests you should use it; I assume the author wouldn't bother writing up an optimization guide without thinking of the thing he goes on to praise later.

    Just my 2 pence.
    Verae, level 60 Cleric @ Blightweald, Guild Master of Tea Club
    I want to fly like an eagle, to the sea.
    I want to fly like an eagle, let my spirit carry me.

  6. #6
    RIFT Community Ambassador the_real_seebs's Avatar
    Join Date
    Jan 2011
    Posts
    16,859

    Default

    Huh, I wouldn't have thought the concrete numbers given for sizes of various objects would be constant. I saw the reference to LuaJIT more as an observation that there's other things to do if you really need performance.

    A little messing around produces, in some cases, noticably different comparative results.
    You can play WoW in any MMO. You don't have to play WoW in RIFT. Oh, and no, RIFT is not a WoW clone. Not having fun any more? Learn to play, noob! I don't speak for Riftui, but I moderate stuff there. Just came back? Welcome back! Here's what's changed. (Updated for 2.5!)

  7. #7
    Telaran
    Join Date
    Mar 2012
    Posts
    83

    Default

    LuaJIT does not only compile, it actually optimizes the code through various methods that probably make some or all of the mentioned enhancements invalid. On the other hand that article talks about extremely minor speed enhancements, that you will never notice unless you have a loop that runs 10000 times a second.

    There is one book that every LUA programmer should read in detail: http://www.lua.org/pil/#online
    It will tell you how to write LUA code, and once you understood it, you know why there is a difference between LUA and most other programming languages. If you feel like it you can grab the 2nd edition from a book store, however the free online version is already extremely valuable to read.

  8. #8
    Plane Walker Imhothar's Avatar
    Join Date
    Feb 2012
    Posts
    439

    Default

    Actually, what is described in the article affects Lua as a language, no matter the implementation.

    LuaJIT cannot change how tables or strings are implemented, as that would make it incompatible with Lua semantics. What the article described, tables, strings, and garbage generation, is still valid in LuaJIt as it is in normal Lua. In both implementations tables, strings and the garbage collector are implemented in C/C++ and this article gives basic knowledge about programming techniques which affect all programming languages which use hash tables, interned strings and a mark-and-sweep garbage collector.

    Accessing globals still requires looking up a hash table (and that part is written in C/C++ in both implementations), meaning accessing a local is always faster as locals get a numeric index and are looked up in an array. And because even LuaJIt is using hash tables, problems like rehashing and hash collisions are still valid.

    What LuaJIT can do is transform the code of a function body to native binary code instead of an interpreted intermediate language and perform local optimizations (e.g. dead code removal, constant propagation, peep-hole, etc) on the code itself, but it does not change how tables, upvalues, strings and the garbage collector work. Due to the very dynamic nature of Lua most global optimization techniques cannot be applied to it and function aliasing is always an issue for any optimization attempts.
    Last edited by Imhothar; 03-12-2012 at 04:59 PM.

  9. #9
    Telaran
    Join Date
    Mar 2012
    Posts
    83

    Default

    What LUAJit does is to transform LUA code into machine code, that is - once transformed - it is as fast as if you had written it in C. In the process of transformation several optimizations are applied, one of the unintentional but convenient ones is that the concept of variables as we know it from the LUA context are gone and replaced with "real" machine-code variables. For the sake of computing it is irrelevant what name you gave to the variable or where it is stored as long as all parts of the code that want to access that variable address the same memory space.

    That makes the entire first chapter of the article mostly irrelevant to the extend that yes, local variables are faster as they can be stored in the CPUs registers, however the gain is below what's measurable. And besides: you never know what compiler optimizations are applied, by some chance your code once transformed magically uses local variables declared outside a loop, because the compiler felt like it is a good way to optimize your code.

    Similar holds true for the rest of the article: yes those changes are faster, but you will only notice it, if you cycle through 100.000 loops a second. And if you do that in a Rift addon, you should probably first work on the design of your implementation before you do minor improvements like concatenating strings through tables. Which is about the same as the author in that article states in the first chapter as rule #1 for compiler optimizations Don't do them. The danger is that if you hand-optimize crappy code for the compiler to speed it up, it will still be crappy afterwards and runs at almost exactly the same slow speed as before, but you wasted probably hours that could have been much better invested into turning the crappy code into good one.

    It is however a sign of good programming style to automatically apply certain good coding stiles like declaring loop variables outside the loop, the gain however is as said not measurable except under extreme situations.

  10. #10
    Plane Walker Imhothar's Avatar
    Join Date
    Feb 2012
    Posts
    439

    Default

    Well as someone who has dealt with the Lua implementation and having a background on program optimization (the stuff compilers do, not the programmers) I can tell you the possibilities of optimizing Lua code are far inferior to the possibilities found in, say C++ or Java. LuaJIT cannot optimize away the lookup of a global variable in the environment's hash table. It cannot eliminate the creation of heavy values if they aren't local (an even then only to a certain degree). Upvalues and closures still require an indirection through lookup tables and strings are implemented in Lua and LuaJIT in C/C++ code. What LuaJIT may do is optimize one concatenation command (like a..b..c..d), but not in for loops (as shown in the article) if it doesn't unroll the loops.

    The optimizations it can do without changing semantics are limited, that is why the article still holds true. The table, string and GC manipulation is present as C code in Lua, what is not compiled is only how and when they get involved, obviously. This means, if you can avoid creating hundreds of tables then Lua as well as LuaJIT will both profit by doing so because the table creation code (which is slower than executing the opcode to create it) is coded in C/C++ in both implementations.

    And yes, I do agree that optimizations should only be done if necessary.

    Premature optimization is the root of all evil!

  11. #11
    Telaran
    Join Date
    Mar 2012
    Posts
    83

    Default

    That is surprising, I would have expected the JIT to be able to optimize much more as other JITs do as well. What is the reason for those strange limitations?

  12. #12
    Plane Walker Imhothar's Avatar
    Join Date
    Feb 2012
    Posts
    439

    Default

    For one, everything is arranged in hash tables, meaning their lookup locations in memory aren't static as you can create and delete globals as you please, possibly causing table rehashing. Other languages can assign each global a fixed memory address and use that for referencing it. That is not possible in Lua. The compiler can precalculate the hash value of "x" when encountering something like t.x but it cannot short-circuit the fetching of its value because the location is dynamic.
    Code:
    x = something
    ...
    y = x -- not only the value of x might have changed but also it's type (int -> string) or location in the table t
    Second, functions are first class values. Calling foo() a second time might call something different than it did the first time. The compiler cannot analyze (in a proper amount of time) whether the function foo is currently pointing to changes any globals that have been fetched to registers prior to the call. C/C++ optimizers have the same problem with function pointers / virtual methods, invalidating all registers containing globals after an indirect method call if there are no #pragmas to help. Static code analysis can improve that, but I don't know whether LuaJIT could do that at runtime.

    Third, creating many small tables is simply a garbage collection problem. The compiler might attempt on reusing tables which are no longer referencible, but that's only a minor improvement. GC pressure is an issue in all garbage collected languages/runtimes.

    Fourth, strings are immutable. The compiler can optimize code like a..b..c..d by looking up each operand's length, summing up the final string length and creating only one string (instead of three). Only doable for static concatenations where the number of operands is known at compile time. But if the concatenation is done inside a for loop with a dynamic number of iterations this shortcut is only possible if partial loop unrolling is done. Table.concat is written in C and can thus loop through all string and create only one final string instead of (n-1) if written in a Lua for loop because it can manipulate memory directly, and, from the VM's point of view, it is an atomic operation.
    Last edited by Imhothar; 03-15-2012 at 09:04 AM.

  13. #13
    RIFT Community Ambassador the_real_seebs's Avatar
    Join Date
    Jan 2011
    Posts
    16,859

    Default

    I would think that at least some functions could be verified not to be referring to any globals, and those could be simplified a lot.

    I did notice that the ratios between different things were frequently different in Rift than the optimization article reports for some other Lua implementation. The basic direction of differences seems stable.

    But yes, Lua's a hard language to optimize all that much, just because everything's dynamic.
    You can play WoW in any MMO. You don't have to play WoW in RIFT. Oh, and no, RIFT is not a WoW clone. Not having fun any more? Learn to play, noob! I don't speak for Riftui, but I moderate stuff there. Just came back? Welcome back! Here's what's changed. (Updated for 2.5!)

  14. #14
    Plane Walker Imhothar's Avatar
    Join Date
    Feb 2012
    Posts
    439

    Default

    Functions, which access neither globals nor up values or any tables (metamethods can screw you up totally). There's also the question whether the compiler should check function values at runtime (that takes time, too), because every non-local function could point to anything. Hell, even tables can be called if they have an appropriate metamethod. So, just because you write foo() doesn't mean the compiler can expect foo to be a function. Then, it could be a C function being called where the compiler has zero information about which values it manipulates, voiding any register caching assumptions. All this is unknown at compile time if foo is non-local or a local which is assigned new values after its creation.

  15. #15
    Telaran
    Join Date
    Mar 2012
    Posts
    83

    Default

    The long version makes a lot of sense, thank you.

    Assuming that variables can change at any time inside and outside of LUA together with the option of dynamically created functions that could possibly change any such global without any hint for the compiler before actual runtime makes it difficult to impossible to optimize that. Now I get why you local everything in your code as well. ;)

    However one statement still stands: don't do compiler optimizations unless you really know what you are doing.

+ Reply to Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts