Lua for Time Travel (!)

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Lua for Time Travel (!)

Joseph 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 / [hidden email]
------------------------------------------------------------------------

Reply | Threaded
Open this post in threaded view
|

Re: Lua for Time Travel (!)

Gabríel Arthúr Pétursson
The os.clock function uses the 'clock' system call. On that particular
system you refer to, `clock_t`, the return value of clock, is defined
as a 32-bit integer.

What you're seeing is that integer wrapping around due to overflow.

Reply | Threaded
Open this post in threaded view
|

Re: Lua for Time Travel (!)

Joseph Manning
On 2017-Jan-25 (Wed) at 13:29 (+0000), Gabríel Arthúr Pétursson wrote:

>> The os.clock function uses the 'clock' system call. On that particular
>> system you refer to, `clock_t`, the return value of clock, is defined
>> as a 32-bit integer.
>>
>> What you're seeing is that integer wrapping around due to overflow.

Gabriel,

   Thanks for your very prompt and clear explanation
   ( even if it's disappointingly reasonable! ).

   It's a little surprising that the upper limit for 'os.clock( )'
   is so small, at least on a 32-bit computer.  But good to know.

Joseph

------------------------------------------------------------------------
Joseph Manning / Computer Science / UCC Cork Ireland / [hidden email]
------------------------------------------------------------------------

Reply | Threaded
Open this post in threaded view
|

Re: Lua for Time Travel (!)

William Ahern
In reply to this post by Joseph Manning
On Wed, Jan 25, 2017 at 01:21:36PM +0000, Joseph Manning wrote:

> 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 a defect ticket for POSIX discussing the overflow issue.

  http://austingroupbugs.net/view.php?id=686

The issue was brought up with the C committee. (See DR 437 in
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1764.pdf) But they want to
wait and see what solutions the POSIX people suggest. Alas, issue #686
hasn't seen any activity since then.

In C I just explicitly type cast clock_t values (each operand individually)
to unsigned long, and everything just magically works because of modulo
arithmetic. But I'm making assumptions about the platform--that it's two's
complement and that unsigned long is the corresponding unsigned type for
clock_t. I really only use it for debugging and quick benchmarking. But as
mentioned in that ticket there's no [easy] portable way to figure out which
unsigned type to convert to. For Lua you'd probably have to use a function
with conditional logic, just like a portable C solution would likely use.

Usually for this sort of thing it's best to use the system's monotonic
clock--clock_gettime(CLOCK_MONOTONIC) on POSIX systems. On modern Linux
systems the granularity and overhead will be the same as clock().[1]
clock_gettime returns a struct timespec, which is also now the preferred
type for time intervals in the latest C standard, C11.


[1] clock() is implemented as clock_gettime(CLOCK_PROCESS_CPUTIME_ID). And
both CLOCK_PROCESS_CPUTIME_ID and CLOCK_MONOTONIC perform pretty much the
same operations--query the CPU TSC, read some cached values, perform the
arithmetic.

Reply | Threaded
Open this post in threaded view
|

Re: Lua for Time Travel (!)

Sean Conner
It was thus said that the Great William Ahern once stated:

> On Wed, Jan 25, 2017 at 01:21:36PM +0000, Joseph Manning wrote:
> > 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 a defect ticket for POSIX discussing the overflow issue.
>
>   http://austingroupbugs.net/view.php?id=686
>
> The issue was brought up with the C committee. (See DR 437 in
> http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1764.pdf) But they want to
> wait and see what solutions the POSIX people suggest. Alas, issue #686
> hasn't seen any activity since then.
>
> In C I just explicitly type cast clock_t values (each operand individually)
> to unsigned long, and everything just magically works because of modulo
> arithmetic. But I'm making assumptions about the platform--that it's two's
> complement and that unsigned long is the corresponding unsigned type for
> clock_t. I really only use it for debugging and quick benchmarking. But as
> mentioned in that ticket there's no [easy] portable way to figure out which
> unsigned type to convert to. For Lua you'd probably have to use a function
> with conditional logic, just like a portable C solution would likely use.
>
> Usually for this sort of thing it's best to use the system's monotonic
> clock--clock_gettime(CLOCK_MONOTONIC) on POSIX systems. On modern Linux
> systems the granularity and overhead will be the same as clock().[1]
> clock_gettime returns a struct timespec, which is also now the preferred
> type for time intervals in the latest C standard, C11.
>
>
> [1] clock() is implemented as clock_gettime(CLOCK_PROCESS_CPUTIME_ID). And
> both CLOCK_PROCESS_CPUTIME_ID and CLOCK_MONOTONIC perform pretty much the
> same operations--query the CPU TSC, read some cached values, perform the
> arithmetic.

  I have a Lua module [1] that calls clock_gettime(), but there's no
LuaRocks spec for it.

  -spc

[1] https://github.com/spc476/lua-conmanorg/blob/master/src/clock.c

Reply | Threaded
Open this post in threaded view
|

Re: Lua for Time Travel (!)

Joseph Manning
In reply to this post by Gabríel Arthúr Pétursson
On Wed, January 25, 2017 13:29, Gabríel Arthúr Pétursson wrote:

>> The os.clock function uses the 'clock' system call. On that particular
>> system you refer to, `clock_t`, the return value of clock, is defined
>> as a 32-bit integer.
>>
>> What you're seeing is that integer wrapping around due to overflow.

Hello again,

   If I may briefly follow up on my original post, here's a vastly
   simpler program that illustrates the issue:

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

local prevclock, thisclock = 0.0, 0.0

repeat
   prevclock = thisclock
   thisclock = os.clock( )
until thisclock < 0

print( prevclock, thisclock )

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

   On a 32-bit computer, we get:

$ lua clocktest.lua
2147.483647 -2147.483647

   So yes indeed, the value returned by 'os.clock( )' wraps around
   after 2^31-1 microseconds, nicely confirming Gabriel's explanation.

Joseph

PS: The Royal Society for the Prevention of Cruelty to Computers
    asks that you kindly refrain from running the above program
    on a 64-bit computer :-)

------------------------------------------------------------------------
Joseph Manning / Computer Science / UCC Cork Ireland / [hidden email]
------------------------------------------------------------------------



Reply | Threaded
Open this post in threaded view
|

Re: Lua for Time Travel (!)

Rena
In reply to this post by William Ahern
On Wed, Jan 25, 2017 at 3:25 PM, William Ahern <[hidden email]> wrote:
On Wed, Jan 25, 2017 at 01:21:36PM +0000, Joseph Manning wrote:
> 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 a defect ticket for POSIX discussing the overflow issue.

  http://austingroupbugs.net/view.php?id=686

The issue was brought up with the C committee. (See DR 437 in
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1764.pdf) But they want to
wait and see what solutions the POSIX people suggest. Alas, issue #686
hasn't seen any activity since then.

In C I just explicitly type cast clock_t values (each operand individually)
to unsigned long, and everything just magically works because of modulo
arithmetic. But I'm making assumptions about the platform--that it's two's
complement and that unsigned long is the corresponding unsigned type for
clock_t. I really only use it for debugging and quick benchmarking. But as
mentioned in that ticket there's no [easy] portable way to figure out which
unsigned type to convert to. For Lua you'd probably have to use a function
with conditional logic, just like a portable C solution would likely use.

Usually for this sort of thing it's best to use the system's monotonic
clock--clock_gettime(CLOCK_MONOTONIC) on POSIX systems. On modern Linux
systems the granularity and overhead will be the same as clock().[1]
clock_gettime returns a struct timespec, which is also now the preferred
type for time intervals in the latest C standard, C11.


[1] clock() is implemented as clock_gettime(CLOCK_PROCESS_CPUTIME_ID). And
both CLOCK_PROCESS_CPUTIME_ID and CLOCK_MONOTONIC perform pretty much the
same operations--query the CPU TSC, read some cached values, perform the
arithmetic.


Perhaps it would be ideal for Lua to automatically save the previous result of clock() and subtract it from the next call? Or would that be too different from the underlying API?

--
Sent from my Game Boy.
Reply | Threaded
Open this post in threaded view
|

Re: Lua for Time Travel (!)

Ross Berteig
On 1/25/2017 2:49 PM, Rena wrote:
On Wed, Jan 25, 2017 at 3:25 PM, William Ahern <[hidden email]> wrote:
On Wed, Jan 25, 2017 at 01:21:36PM +0000, Joseph Manning wrote:
> Dear All,
>
>    Have you ever wondered how the Lua Team manage to retain their
>    ever-youthful good looks?

I always assumed there were some paintings in a vault that are aging slowly...

> ....
>    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.
....

In C I just explicitly type cast clock_t values (each operand individually)
to unsigned long, and everything just magically works because of modulo
arithmetic. But I'm making assumptions about the platform--that it's two's
complement and that unsigned long is the corresponding unsigned type for
clock_t. I really only use it for debugging and quick benchmarking. But as
mentioned in that ticket there's no [easy] portable way to figure out which
unsigned type to convert to. For Lua you'd probably have to use a function
with conditional logic, just like a portable C solution would likely use.

According to the clock() manpage [1], CLOCKS_PER_SEC effectively must be the constant 1000000. I'm not sure why clock_t is permitted to be signed, but it clearly is a signed type on 32-bit x86 linux. Even if unsigned, clock() rolls over after a little less than 72 minutes or 2^32 microseconds.

So perhaps Lua's implementation of os.clock() ought to cast the result of clock() to a platform-specific sized unsigned value since by the time it has been converted to a floating point value it is too late for the Lua code to do much with it in a portable way when it goes negative.

....
Perhaps it would be ideal for Lua to automatically save the previous result of clock() and subtract it from the next call? Or would that be too different from the underlying API?

If you did anything like this, it would be to remember the value returned from the first call to clock() and subtract that from all subsequent calls, and possibly make that first call to clock() as part of initializing the os module so that 0 is close to the actual start of the program. The Lua manual [2] does say "Returns an approximation of the amount in seconds of CPU time used by the program" so taming the fact that POSIX permits clock() to return anything at all at the start of the process might be arguably the correct thing to do. Or relax the documentation to merely claim that os.clock() will be monotonic until it wraps, which might be in 72 minutes, or until the heat death of the universe, depending.

Either way, it does seem like a bug that os.clock() could return a negative number, and fixing that would not be difficult. Preventing the wrap to zero on 32-bit systems would be substantially more difficult, technically possible, and likely completely not worth the effort. It could also be done in pure Lua, if you can make the assumption that os.clock() will be called often enough.

[1]: https://linux.die.net/man/3/clock
[2]: https://www.lua.org/manual/5.3/manual.html#6.9
-- 
Ross Berteig                               [hidden email]
Cheshire Engineering Corp.           http://www.CheshireEng.com/
+1 626 303 1602