|Portada|Blog|Space|

Benchmarks for basic stuff. These tests were run on a rpi 3 (Cortex A53). The code is available here, with the accepted results being those where the average time was within the minimum time and its %105 (low variance only achievable on low loadavg). ######## TABLE ITERATION ######## There are several methods that allow iteration of tables in lua, specially on "array" tables where the keys are the integers {1, 2, ..., n}. Let's compare this kind of tables first adding an array of random numbers, via the following alternatives: -> range: for i = 1, #t do local v=t[i]; ... end -> ipairs: for i, v in ipairs(t) do ... end -> pairs: for k, v in ipairs(t) do ... end range results: #t | lua 5.1 | lua 5.2 | lua 5.3 | luajit 10 | 136ns·#t | 157ns·#t | 127ns·#t | 11.6ns·#t 100 | 118ns·#t | 144ns·#t | 109ns·#t | 7.91ns·#t 1000 | 117ns·#t | 161ns·#t | 107ns·#t | 7.54ns·#t ipairs results: #t | lua 5.1 | lua 5.2 | lua 5.3 | luajit 10 | 348ns·#t | 348ns·#t | 331ns·#t | 17.2ns·#t 100 | 292ns·#t | 291ns·#t | 276ns·#t | 9.22ns·#t 1000 | 289ns·#t | 301ns·#t | 270ns·#t | 8.42ns·#t pairs results: #t | lua 5.1 | lua 5.2 | lua 5.3 | luajit 10 | 328ns·#t | 345ns·#t | 341ns·#t | 72.1ns·#t 100 | 270ns·#t | 291ns·#t | 280ns·#t | 53.7ns·#t 1000 | 263ns·#t | 279ns·#t | 277ns·#t | 50.4ns·#t Comments: Who have thought ipairs would be a little slower than pairs on lua5.1, if anything one would have expected the opposite. If we now compare the results to the tight loop of the equivalent native code, we can see that it should take about 4 cycles (3.3ns·#t on a rpi3). Note that r2 is the vector's upper limit, r3 the array pointer, d6 the current number to add and d7 the accumulator. The instruction latency, pipelines used and throughput is also included. address, bytes, instruction, args, | lat (pip) thr 1060c: ecb36b02 vldmia r3!, {d6} | 4 (L) 1 loading 10610: e1530002 cmp r3, r2 | 1 (I) 1 comparing 10614: ee377b06 vadd.f64 d7, d7, d6 | 5 (F) 2 add 10618: 1afffffb bne 1060c <fn+0x24> | 1 (B) 1 repeat until zero Explaining why we got 4 cycles = 3.3ns per addition, even though this code could be optimized a little bit :) Let's see how luajit does in its best run: The registers used are: r0, iteration limit (1000 in this case); r4, variable "i"'s current value; r6, array address; r11, address of current element to add; d14, current element to add; d15, accumulator. The remaining register, lr, is used for holding the upper 32-bits of the current 64-bit floating point "number" to add, by adding 15=0xf and checking the carry flag the code can detect the case when the all bits 31~4 are 1 and at least one of the bits 0~3 is true, branching to 0x540020 on that case. You may wonder, what's so special about those bits? Well, as luajit's lj_obj.h explains IEEE-754 64-bit floating point numbers (standard numbers) detect as a special number NaN (Not a Number really) the values between: 0x7ff0_0000_0000_0001 = inf + 1, and 0x7fff_ffff_ffff_ffff, and for -NaN: 0xfff0_0000_0000_0001 = -inf - 1, and 0xffff_ffff_ffff_ffff. However, of those 2*(2**52 - 1) possible NaNs only a few are used, having those with the most significant word > 0xfff8_0000 available for other uses! Luajit uses those bits to store the type of any other (non-number) object, for nil the value ~0 = -1 = 0xffff_ffff is used, for false ~1 = -2 = 0xffff_fffe, ~4 for strings, etc... on these cases the least significant word is used as well (e.g. for storing the address of the strings), so that now storing a number consumes the same amount of memory as storing a reference to an object. 547ea8: add r11, r6, r4, lsl #3 | address r11 <- r6 + r4*8 547eac: ldr lr, [r11, #4] | load the into lr 547eb0: vldr d14, [r11] | load the full 64-bit number into d14 547eb4: cmn lr, #15 | ensure the number was really a number 547eb8: blcs 0x540020 | handling the special case otherwise 547ebc: vadd.f64 d15, d14, d15 | add d14 into the accumulator 547ec0: add r4, r4, #1 | advance the index to the next position 547ec4: cmp r4, r0 | compare to the limit 547ec8: ble 0x547ea8 | and repeat while it is not surpassed This is how luajit achieves near optimum performance while having to deal with heterogeneous arrays. But on non contiguous arrays aka hash tables, the result is very different, the next test deals with the iteration of a table where the keys are now the odd numbers {1, 3, ..., 2n-1}. pairs_odd results: #t | lua 5.1 | lua 5.2 | lua 5.3 | luajit 10 | 494ns·#t | 510ns·#t | 438ns·#t | 85ns·#t 100 | 432ns·#t | 454ns·#t | 388ns·#t | 63ns·#t 1000 | 429ns·#t | 444ns·#t | 389ns·#t | 57ns·#t range_odd results: #t | lua 5.1 | lua 5.2 | lua 5.3 | luajit 10 | 239ns·#t | 285ns·#t | 148ns·#t | 11.9ns·#t 100 | 230ns·#t | 278ns·#t | 131ns·#t | 7.92ns·#t 1000 | 231ns·#t | 277ns·#t | 140ns·#t | 7.54ns·#t Looking at the machine code generated by luajit this time, the only difference occurs in the add r4, r4, #1 line, that now adds #2, that's why the performance was so similar; even though the array is not contiguous, luajit stores it in a plain array interleaved with nils. ######## TABLE INSERTION ######## -> insert: table.insert(t, item) -> insert2: local insert = table.insert; insert(t, item) -> len: t[#t + 1] = item -> len2: t[tnext], tnext = item, tnext + 1 insert results: #t | lua 5.1 | lua 5.2 | lua 5.3 | luajit 10 | 541ns·#t | 658ns·#t | 645ns·#t | 130ns·#t 100 | 542ns·#t | 656ns·#t | 645ns·#t | 130ns·#t 1000 | 537ns·#t | 654ns·#t | 641ns·#t | 127ns·#t insert2 results: #t | lua 5.1 | lua 5.2 | lua 5.3 | luajit 10 | 418ns·#t | 513ns·#t | 519ns·#t | 127ns·#t 100 | 425ns·#t | 516ns·#t | 520ns·#t | 129ns·#t 1000 | 424ns·#t | 518ns·#t | 520ns·#t | 129ns·#t len results: #t | lua 5.1 | lua 5.2 | lua 5.3 | luajit 10 | 317ns·#t | 360ns·#t | 328ns·#t | 127ns·#t 100 | 318ns·#t | 366ns·#t | 331ns·#t | 130ns·#t 1000 | 320ns·#t | 367ns·#t | 332ns·#t | 130ns·#t len2 results: #t | lua 5.1 | lua 5.2 | lua 5.3 | luajit 10 | 141ns·#t | 176ns·#t | 140ns·#t | 24ns·#t 100 | 144ns·#t | 180ns·#t | 141ns·#t | 27ns·#t 1000 | 144ns·#t | 180ns·#t | 141ns·#t | 28ns·#t ######## STRING ITERATION ######## -> gsub: for c in s:gmatch '.' do ... end -> sub: for i = 1, #s do local c = s:sub(i, i); ... end -> byte: for i = 1, #s do local b = s:byte(i, i); ... end