Lua for Time Travel (!)
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Lua for Time Travel (!)
- From: "Joseph Manning" <manning@...>
- Date: 2017年1月25日 13:21:36 +0000
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
------------------------------------------------------------------------