Lua for Time Travel (!)

["Joseph Manning" <manning@...>]

Dear All,

   Have you ever wondered how the Lua Team manage to retain their
   ever-youthful good looks?

   Do you want to become mega-rich like Biff in Back To The Future II,
   by placing bets when you already know the outcome?

   Or would you simply like to run your programs so fast that they
   actually finish before they've even started?

   Well, these are all now possible, by using Lua for Time Travel !!!

   ( ... takes his medication, and a semblance of sanity returns ... )

   So, I was timing a section of code by wrapping it in calls to
   'os.clock( )', and under certain conditions, the second such call
   returned a value that was substantially smaller than the first --
   in fact, it returned a negative value, which should never happen.

   Here's the program:


------------------------------------------------------------------------

local bitsperint = 64

local ones = { }
local mask = 1

for i = 0, bitsperint - 1 do
   ones[ i ] = mask
   mask      = mask << 1
   end

------------------------------------------------------------------------

local L1size = tonumber( arg[ 1 ] )

local L2     = { }

for i = 0, L1size // bitsperint do
   L2[ i ] = 0
   end

------------------------------------------------------------------------

local L1 = { }

setmetatable( L1, { __newindex = function ( _, n, _ )
                                 -- Set bit 'n' of 'L2' to 1
                                    local i1 = n // bitsperint
                                    local i2 = n %  bitsperint
                                    L2[ i1 ] = L2[ i1 ] | ones[ i2 ]
                                    end } )

------------------------------------------------------------------------

local start = os.clock( )

for n = 1, L1size do
   L1[ n ] = 1
   end

local finish = os.clock( )

print( start, finish, finish - start )

------------------------------------------------------------------------


   Yes, by itself it's a silly inefficient way of setting every bit
   in every element of 'L2' to 1 -- but it's derived from a genuine
   use-case ( a compact Sieve of Eratosthenes which packs 64 booleans
   into an integer ).

   It gave the following output:

$ time lua timetest.lua 2000000000
6.086058	-1941.149055	-1947.235113

real	39m15.992s
user	39m11.580s
sys	0m2.304s

   So although it actually ran for over 39 minutes, it reports taking
   -1947 seconds = -32.45 minutes, according to the 'os.clock( )' calls.

   Note the following:

   - this strange behaviour was fully reproducible across many tests,
     with the timing numbers varying only slightly

   - the value  L1size = 2000000000  made the program consume 79.1%
     of the computer's memory ( according to the Linux 'top' command )

   - when 'L1size' was reduced to 1000000000, the behaviour was normal,
     with the program reporting a running time of 1225 seconds

   - this might(?) hint(?) that a memory location is being overwritten?

   - the strange behaviour occurred only on a 32-bit computer; I could
     not reproduce it on a 64-bit computer

   - I'm running the Debian 8 'jessie' version of Linux, which has the
     Linux 3.16.0-4-686-pae kernel

   - the odd results happened under both Lua 5.3.1 from Debian 8, and
     the latest Lua 5.3.4-rc3, built with a bog-standard 'make linux'

   Can anyone else reproduce these results, or suggest an explanation?

Thanks! -- Joseph ( Time Lord )

------------------------------------------------------------------------
Joseph Manning / Computer Science / UCC Cork Ireland / manning@cs.ucc.ie
------------------------------------------------------------------------