Re: [Tarantool-patches] [PATCH v1 luajit 01/41] perf: add LuaJIT-test-cleanup perf suite

[Sergey Bronnikov via Tarantool-patches <tarantool-patches@dev.tarantool.org>]

[-- Attachment #1: Type: text/plain, Size: 22688 bytes --]

Hi, Sergey,

thanks for the patch!

This is a big step forward for LuaJIT performance testing.

Please take a look on the comments below.

Sergey

On 10/24/25 13:50, Sergey Kaplun wrote:
> This patch introduces the LuaJIT-test-cleanup bench suite [1] into our
s/bench/benchmark/
> LuaJIT fork source tree. To provide relatable reprodusible results

did not get it: "relatable"

s/reprodusible/reproducible/

> several benchmarks need to be adjusted. However, to be sure we initially use
> the valid suite, everything in the <perf/LuaJIT-benches> directory is
> moved intact.
>
> [1]:https://github.com/LuaJIT/LuaJIT-test-cleanup/tree/014708b/bench
> ---
>   .luacheckrc                                |    1 +
>   perf/LuaJIT-benches/PARAM_arm.txt          |   29 +
>   perf/LuaJIT-benches/PARAM_mips.txt         |   29 +
>   perf/LuaJIT-benches/PARAM_ppc.txt          |   29 +
>   perf/LuaJIT-benches/PARAM_x86.txt          |   29 +
>   perf/LuaJIT-benches/SUMCOL_1.txt           | 1000 ++++++++++++++++++++
>   perf/LuaJIT-benches/TEST_md5sum.txt        |   20 +
>   perf/LuaJIT-benches/array3d.lua            |   59 ++
>   perf/LuaJIT-benches/binary-trees.lua       |   47 +
>   perf/LuaJIT-benches/chameneos.lua          |   68 ++
>   perf/LuaJIT-benches/coroutine-ring.lua     |   42 +
>   perf/LuaJIT-benches/euler14-bit.lua        |   22 +
>   perf/LuaJIT-benches/fannkuch.lua           |   50 +
>   perf/LuaJIT-benches/fasta.lua              |   95 ++
>   perf/LuaJIT-benches/k-nucleotide.lua       |   58 ++
>   perf/LuaJIT-benches/life.lua               |  111 +++
>   perf/LuaJIT-benches/mandelbrot-bit.lua     |   33 +
>   perf/LuaJIT-benches/mandelbrot.lua         |   23 +
>   perf/LuaJIT-benches/md5.lua                |  183 ++++
>   perf/LuaJIT-benches/meteor.lua             |  220 +++++
>   perf/LuaJIT-benches/nbody.lua              |  119 +++
>   perf/LuaJIT-benches/nsieve-bit-fp.lua      |   37 +
>   perf/LuaJIT-benches/nsieve-bit.lua         |   27 +
>   perf/LuaJIT-benches/nsieve.lua             |   21 +
>   perf/LuaJIT-benches/partialsums.lua        |   29 +
>   perf/LuaJIT-benches/pidigits-nogmp.lua     |  100 ++
>   perf/LuaJIT-benches/ray.lua                |  135 +++
>   perf/LuaJIT-benches/recursive-ack.lua      |    8 +
>   perf/LuaJIT-benches/recursive-fib.lua      |    7 +
>   perf/LuaJIT-benches/revcomp.lua            |   37 +
>   perf/LuaJIT-benches/scimark-2010-12-20.lua |  400 ++++++++
>   perf/LuaJIT-benches/scimark-fft.lua        |    1 +
>   perf/LuaJIT-benches/scimark-lu.lua         |    1 +
>   perf/LuaJIT-benches/scimark-sor.lua        |    1 +
>   perf/LuaJIT-benches/scimark-sparse.lua     |    1 +
>   perf/LuaJIT-benches/scimark_lib.lua        |  297 ++++++
>   perf/LuaJIT-benches/series.lua             |   34 +
>   perf/LuaJIT-benches/spectral-norm.lua      |   40 +
>   perf/LuaJIT-benches/sum-file.lua           |    6 +
>   39 files changed, 3449 insertions(+)
>   create mode 100644 perf/LuaJIT-benches/PARAM_arm.txt
>   create mode 100644 perf/LuaJIT-benches/PARAM_mips.txt
>   create mode 100644 perf/LuaJIT-benches/PARAM_ppc.txt
>   create mode 100644 perf/LuaJIT-benches/PARAM_x86.txt
>   create mode 100644 perf/LuaJIT-benches/SUMCOL_1.txt
>   create mode 100644 perf/LuaJIT-benches/TEST_md5sum.txt
>   create mode 100644 perf/LuaJIT-benches/array3d.lua
>   create mode 100644 perf/LuaJIT-benches/binary-trees.lua
>   create mode 100644 perf/LuaJIT-benches/chameneos.lua
>   create mode 100644 perf/LuaJIT-benches/coroutine-ring.lua
>   create mode 100644 perf/LuaJIT-benches/euler14-bit.lua
>   create mode 100644 perf/LuaJIT-benches/fannkuch.lua
>   create mode 100644 perf/LuaJIT-benches/fasta.lua
>   create mode 100644 perf/LuaJIT-benches/k-nucleotide.lua
>   create mode 100644 perf/LuaJIT-benches/life.lua
>   create mode 100644 perf/LuaJIT-benches/mandelbrot-bit.lua
>   create mode 100644 perf/LuaJIT-benches/mandelbrot.lua
>   create mode 100644 perf/LuaJIT-benches/md5.lua
>   create mode 100644 perf/LuaJIT-benches/meteor.lua
>   create mode 100644 perf/LuaJIT-benches/nbody.lua
>   create mode 100644 perf/LuaJIT-benches/nsieve-bit-fp.lua
>   create mode 100644 perf/LuaJIT-benches/nsieve-bit.lua
>   create mode 100644 perf/LuaJIT-benches/nsieve.lua
>   create mode 100644 perf/LuaJIT-benches/partialsums.lua
>   create mode 100644 perf/LuaJIT-benches/pidigits-nogmp.lua
>   create mode 100644 perf/LuaJIT-benches/ray.lua
>   create mode 100644 perf/LuaJIT-benches/recursive-ack.lua
>   create mode 100644 perf/LuaJIT-benches/recursive-fib.lua
>   create mode 100644 perf/LuaJIT-benches/revcomp.lua
>   create mode 100644 perf/LuaJIT-benches/scimark-2010-12-20.lua
>   create mode 100644 perf/LuaJIT-benches/scimark-fft.lua
>   create mode 100644 perf/LuaJIT-benches/scimark-lu.lua
>   create mode 100644 perf/LuaJIT-benches/scimark-sor.lua
>   create mode 100644 perf/LuaJIT-benches/scimark-sparse.lua
>   create mode 100644 perf/LuaJIT-benches/scimark_lib.lua
>   create mode 100644 perf/LuaJIT-benches/series.lua
>   create mode 100644 perf/LuaJIT-benches/spectral-norm.lua
>   create mode 100644 perf/LuaJIT-benches/sum-file.lua
>
> diff --git a/.luacheckrc b/.luacheckrc
> index 19098dd9..35824875 100644
> --- a/.luacheckrc
> +++ b/.luacheckrc
> @@ -16,6 +16,7 @@ files['test/tarantool-tests/'] = {
>   -- test suites and need to be coherent with the upstream.
>   exclude_files = {
>     'dynasm/',
> +  'perf/LuaJIT-benches/',

Please don't do this. It is better to ignore by code number and at least

some groups of warnings in the code.

--- a/.luacheckrc
+++ b/.luacheckrc
@@ -12,11 +12,29 @@ files['test/tarantool-tests/'] = {
    read_globals = {'_TARANTOOL'},
  }

+files["perf/LuaJIT-benches/*.lua"] = {
+  ignore = {
+    "111",
+    "112",
+    "113",
+    "211",
+    "212",
+    "213",
+    "231",
+    "413",
+    "432",
+    "421",
+    "431",
+    "612",
+    "631",
+  }
+}
+
  -- These files are inherited from the vanilla LuaJIT or different
  -- test suites and need to be coherent with the upstream.

>     'src/',
>     'test/LuaJIT-tests/',
>     'test/PUC-Rio-Lua-5.1-tests/',
> diff --git a/perf/LuaJIT-benches/PARAM_arm.txt b/perf/LuaJIT-benches/PARAM_arm.txt
> new file mode 100644
> index 00000000..a07fd010
> --- /dev/null
> +++ b/perf/LuaJIT-benches/PARAM_arm.txt
> @@ -0,0 +1,29 @@
> +array3d 200

It is not clear why exactly these parameters are used.

Should we change them?

it deserves a comment in commit message

> +binary-trees 13
> +chameneos 1e6
> +coroutine-ring 3e6
> +euler14-bit 5e6
> +fannkuch 10
> +fasta 2e6
> +k-nucleotide 5e5 FASTA_500000
> +life
> +mandelbrot 2000
> +mandelbrot-bit 2000
> +md5 5000
> +nbody 1e6
> +nsieve 9
> +nsieve-bit 9
> +nsieve-bit-fp 9
> +partialsums 2e6
> +pidigits-nogmp 2000
> +ray 4
> +recursive-ack 9
> +recursive-fib 37
> +revcomp 1e6 FASTA_1000000
> +scimark-fft 2000
> +scimark-lu 300
> +scimark-sor 5000
> +scimark-sparse 5e3
> +series 1500
> +spectral-norm 1000
> +sum-file 1000 SUMCOL_1000
> diff --git a/perf/LuaJIT-benches/PARAM_mips.txt b/perf/LuaJIT-benches/PARAM_mips.txt
> new file mode 100644
> index 00000000..e6bcadba
> --- /dev/null
> +++ b/perf/LuaJIT-benches/PARAM_mips.txt

Do we really need parameters for unsupported platforms (MIPS, x86, ppc)?

it deserves a comment in commit message

> @@ -0,0 +1,29 @@
> +array3d 50
> +binary-trees 10
> +chameneos 5e4
> +coroutine-ring 2e5
> +euler14-bit 2e4
> +fannkuch 8
> +fasta 2e4
> +k-nucleotide 1e4 FASTA_10000
> +life
> +mandelbrot 150
> +mandelbrot-bit 150
> +md5 10
> +nbody 1e4
> +nsieve 4
> +nsieve-bit 4
> +nsieve-bit-fp 2
> +partialsums 5e4
> +pidigits-nogmp 150
> +ray 2
> +recursive-ack 7
> +recursive-fib 29
> +revcomp 5e4 FASTA_50000
> +scimark-fft 20
> +scimark-lu 3
> +scimark-sor 40
> +scimark-sparse 100
> +series 50
> +spectral-norm 100
> +sum-file 100 SUMCOL_100
> diff --git a/perf/LuaJIT-benches/PARAM_ppc.txt b/perf/LuaJIT-benches/PARAM_ppc.txt
> new file mode 100644
> index 00000000..c8319a15
> --- /dev/null
> +++ b/perf/LuaJIT-benches/PARAM_ppc.txt
> @@ -0,0 +1,29 @@
> +array3d 200
> +binary-trees 13
> +chameneos 1e6
> +coroutine-ring 4e6
> +euler14-bit 1e6
> +fannkuch 9
> +fasta 5e5
> +k-nucleotide 1e5 FASTA_100000
> +life
> +mandelbrot 800
> +mandelbrot-bit 800
> +md5 500
> +nbody 1e5
> +nsieve 8
> +nsieve-bit 8
> +nsieve-bit-fp 8
> +partialsums 5e5
> +pidigits-nogmp 800
> +ray 5
> +recursive-ack 9
> +recursive-fib 34
> +revcomp 1e6 FASTA_1000000
> +scimark-fft 500
> +scimark-lu 100
> +scimark-sor 1000
> +scimark-sparse 3000
> +series 1000
> +spectral-norm 200
> +sum-file 1000 SUMCOL_1000
> diff --git a/perf/LuaJIT-benches/PARAM_x86.txt b/perf/LuaJIT-benches/PARAM_x86.txt
> new file mode 100644
> index 00000000..87088d7b
> --- /dev/null
> +++ b/perf/LuaJIT-benches/PARAM_x86.txt
> @@ -0,0 +1,29 @@
> +array3d 300
> +binary-trees 16
> +chameneos 1e7
> +coroutine-ring 2e7
> +euler14-bit 2e7
> +fannkuch 11
> +fasta 25e6
> +k-nucleotide 5e6 FASTA_5000000
> +life
> +mandelbrot 5000
> +mandelbrot-bit 5000
> +md5 20000
> +nbody 5e6
> +nsieve 12
> +nsieve-bit 12
> +nsieve-bit-fp 12
> +partialsums 1e7
> +pidigits-nogmp 5000
> +ray 9
> +recursive-ack 10
> +recursive-fib 40
> +revcomp 5e6 FASTA_5000000
> +scimark-fft 50000
> +scimark-lu 5000
> +scimark-sor 50000
> +scimark-sparse 15e4
> +series 10000
> +spectral-norm 3000
> +sum-file 5000 SUMCOL_5000
> diff --git a/perf/LuaJIT-benches/SUMCOL_1.txt b/perf/LuaJIT-benches/SUMCOL_1.txt
> new file mode 100644
> index 00000000..956aba14
> --- /dev/null
> +++ b/perf/LuaJIT-benches/SUMCOL_1.txt
> @@ -0,0 +1,1000 @@
<snipped>
> diff --git a/perf/LuaJIT-benches/TEST_md5sum.txt b/perf/LuaJIT-benches/TEST_md5sum.txt
> new file mode 100644
> index 00000000..15aa8a1c
> --- /dev/null
> +++ b/perf/LuaJIT-benches/TEST_md5sum.txt
> @@ -0,0 +1,20 @@
> +binarytrees	10	7202f4e13df7abc5ad8c07f05fe9d644
> +chameneos	1e5	a629ce12f63050c6656bce175258cf8f
> +cheapconcr	1000	d29799d1e263810a4db7bbf43ca66499
> +cheapconcw	1000	d29799d1e263810a4db7bbf43ca66499
> +fannkuch	8	51e5e372cbc5471ea8940b20ad782319
> +fasta	1e5	78cd327de6f0a5667da0aa9349888279
> +knucleotide	x	88efb24c1fed533959ed84bb32c88142 <FASTA_10000
> +mandelbrot	200	cc65e64bd553ed18896de1dfe7fae3e5
> +meteor	3000	9a65bb4b0a735ace1eaa4f2628f01026
> +nbody	1e4	e0361c898ba747117ec177f7b3b3359c
> +nsieve	4	767e02c93624995732e151932fa5f304
> +nsievebits	4	767e02c93624995732e151932fa5f304
> +partialsums	1e5	33efb41c72f8ecfb5b36c99e32189a3f
> +pidigits	200	173a11a77bb1e72dd31254a760317428
> +recursive	4	07a47c2d2cf50503b16efda789f84916
> +regexdna	x	fdf3e6e9c599754e1eec3e524ea13fed <FASTA_10000
> +revcomp	x	47de276e2f72519b57b82da39f4c7592 <FASTA_10000
> +spectralnorm 200	25f44bd552ccd9faa0ee2ae5617947e2
> +sumfile	x	2ebd3caa45b31a2e74e436b645eab4b0 <SUMCOL_100
> +
> diff --git a/perf/LuaJIT-benches/array3d.lua b/perf/LuaJIT-benches/array3d.lua
> new file mode 100644
> index 00000000..c10b09b1
> --- /dev/null
> +++ b/perf/LuaJIT-benches/array3d.lua
> @@ -0,0 +1,59 @@
> +
please remove a newline
> +local function array_set(self, x, y, z, p)
> +  assert(x >= 0 and x < self.nx, "x outside PA")
> +  assert(y >= 0 and y < self.ny, "y outside PA")
> +  assert(z >= 0 and z < self.nz, "z outside PA")
> +  local pos = (z*self.ny + y)*self.nx + x
> +  local image = self.image
> +  if self.packed then
> +    local maxv = self.max_voltage
> +    if p > maxv then self.max_voltage = p*2.0 end
> +    local oldp = image[pos] or 0.0 -- Works with uninitialized table, too
> +    if oldp > maxv then p = p + maxv*2.0 end
> +    image[pos] = p
> +  else
> +    image[pos] = p
> +  end
> +  self.changed = true
> +  self.changed_recently = true
> +end
> +
> +local function array_points(self)
> +  local y, z = 0, 0
> +  return function(self, x)
> +    x = x + 1
> +    if x >= self.nx then
> +      x = 0
> +      y = y + 1
> +      if y >= self.ny then
> +	y = 0
> +	z = z + 1
> +	if z >= self.nz then
> +	  return nil, nil, nil
> +	end
> +      end
> +    end
> +    return x, y, z
> +  end, self, 0
> +end
> +
> +local function array_new(nx, ny, nz, packed)
> +  return {
> +    nx = nx, ny = ny, nz = nz,
> +    packed = packed, max_voltage = 0.0,
> +    changed = false, changed_recently = false,
> +    image = {}, -- Preferably use a fixed-type, pre-sized array here.
> +    set = array_set,
> +    points = array_points,
> +  }
> +end
> +
> +local dim = tonumber(arg and arg[1]) or 300 -- Array dimension dim^3
> +local packed = arg and arg[2] == "packed"   -- Packed image or flat
> +local arr = array_new(dim, dim, dim, packed)
> +
> +for x,y,z inarr:points() do
> +arr:set(x, y, z, x*x)
> +end
> +assert(arr.image[dim^3-1] == (dim-1)^2)
> +
trailing newline
> diff --git a/perf/LuaJIT-benches/binary-trees.lua b/perf/LuaJIT-benches/binary-trees.lua
> new file mode 100644
> index 00000000..bf040466
> --- /dev/null
> +++ b/perf/LuaJIT-benches/binary-trees.lua
> @@ -0,0 +1,47 @@
> +
unnecessary newline
> +local function BottomUpTree(item, depth)
> +  if depth > 0 then
> +    local i = item + item
> +    depth = depth - 1
> +    local left, right = BottomUpTree(i-1, depth), BottomUpTree(i, depth)
> +    return { item, left, right }
> +  else
> +    return { item }
> +  end
> +end
> +
> +local function ItemCheck(tree)
> +  if tree[2] then
> +    return tree[1] + ItemCheck(tree[2]) - ItemCheck(tree[3])
> +  else
> +    return tree[1]
> +  end
> +end
> +
> +local N = tonumber(arg and arg[1]) or 0
> +local mindepth = 4
> +local maxdepth = mindepth + 2
> +if maxdepth < N then maxdepth = N end
> +
> +do
> +  local stretchdepth = maxdepth + 1
> +  local stretchtree = BottomUpTree(0, stretchdepth)
> +  io.write(string.format("stretch tree of depth %d\t check: %d\n",
> +    stretchdepth, ItemCheck(stretchtree)))
> +end
> +
> +local longlivedtree = BottomUpTree(0, maxdepth)
> +
> +for depth=mindepth,maxdepth,2 do
> +  local iterations = 2 ^ (maxdepth - depth + mindepth)
> +  local check = 0
> +  for i=1,iterations do
> +    check = check + ItemCheck(BottomUpTree(1, depth)) +
> +            ItemCheck(BottomUpTree(-1, depth))
> +  end
> +  io.write(string.format("%d\t trees of depth %d\t check: %d\n",
> +    iterations*2, depth, check))
> +end
> +
> +io.write(string.format("long lived tree of depth %d\t check: %d\n",
> +  maxdepth, ItemCheck(longlivedtree)))
> diff --git a/perf/LuaJIT-benches/chameneos.lua b/perf/LuaJIT-benches/chameneos.lua
> new file mode 100644
> index 00000000..78b64c3f
> --- /dev/null
> +++ b/perf/LuaJIT-benches/chameneos.lua
> @@ -0,0 +1,68 @@
> +
unnecessary newline
> +local co = coroutine
> +local create, resume, yield = co.create, co.resume, co.yield
> +
> +local N = tonumber(arg and arg[1]) or 10
> +local first, second
> +
> +-- Meet another creature.
> +local function meet(me)
> +  while second do yield() end -- Wait until meeting place clears.
> +  local other = first
> +  if other then -- Hey, I found a new friend!
> +    first = nil
> +    second = me
> +  else -- Sniff, nobody here (yet).
> +    local n = N - 1
> +    if n < 0 then return end -- Uh oh, the mall is closed.
> +    N = n
> +    first = me
> +    repeat yield(); other = second until other -- Wait for another creature.
> +    second = nil
> +    yield() -- Be nice and let others meet up.
> +  end
> +  return other
> +end
> +
> +-- Create a very social creature.
> +local function creature(color)
> +  return create(function()
> +    local me = color
> +    for met=0,1000000000 do
> +      local other = meet(me)
> +      if not other then return met end
> +      if me ~= other then
> +        if me == "blue" then me = other == "red" and "yellow" or "red"
> +        elseif me == "red" then me = other == "blue" and "yellow" or "blue"
> +        else me = other == "blue" and "red" or "blue" end
> +      end
> +    end
> +  end)
> +end
> +
> +-- Trivial round-robin scheduler.
> +local function schedule(threads)
> +  local resume = resume
> +  local nthreads, meetings = #threads, 0
> +  repeat
> +    for i=1,nthreads do
> +      local thr = threads[i]
> +      if not thr then return meetings end
> +      local ok, met = resume(thr)
> +      if met then
> +        meetings = meetings + met
> +        threads[i] = nil
> +      end
> +    end
> +  until false
> +end
> +
> +-- A bunch of colorful creatures.
> +local threads = {
> +  creature("blue"),
> +  creature("red"),
> +  creature("yellow"),
> +  creature("blue"),
> +}
> +
> +io.write(schedule(threads), "\n")
> diff --git a/perf/LuaJIT-benches/coroutine-ring.lua b/perf/LuaJIT-benches/coroutine-ring.lua
> new file mode 100644
> index 00000000..1e8c5ef6
> --- /dev/null
> +++ b/perf/LuaJIT-benches/coroutine-ring.lua
> @@ -0,0 +1,42 @@
> +-- The Computer Language Benchmarks Game
> +--http://shootout.alioth.debian.org/
> +-- contributed by Sam Roberts
> +-- reviewed by Bruno Massa
> +
> +local n         = tonumber(arg and arg[1]) or 2e7
> +
> +-- fixed size pool
> +local poolsize  = 503
> +local threads   = {}
> +
> +-- cache these to avoid global environment lookups
> +local create    = coroutine.create
> +local resume    = coroutine.resume
> +local yield     = coroutine.yield
> +
> +local id        = 1
> +local token     = 0
> +local ok
> +
> +local body = function(token)
> +  while true do
> +    token = yield(token + 1)
> +  end
> +end
> +
> +-- create all threads
> +for id = 1, poolsize do
> +  threads[id] = create(body)
> +end
> +
> +-- send the token
> +repeat
> +  if id == poolsize then
> +    id = 1
> +  else
> +    id = id + 1
> +  end
> +  ok, token = resume(threads[id], token)
> +until token == n
> +
> +io.write(id, "\n")
> diff --git a/perf/LuaJIT-benches/euler14-bit.lua b/perf/LuaJIT-benches/euler14-bit.lua
> new file mode 100644
> index 00000000..537f2bf3
> --- /dev/null
> +++ b/perf/LuaJIT-benches/euler14-bit.lua
> @@ -0,0 +1,22 @@
> +
unnecessary newline. here and below
> +local bit = require("bit")
> +local bnot, bor, band = bit.bnot, bit.bor, bit.band
> +local shl, shr = bit.lshift, bit.rshift
> +
> +local N = tonumber(arg and arg[1]) or 10000000
> +local cache, m, n = { 1 }, 1, 1
> +if arg and arg[2] then cache = nil end
> +for i=2,N do
> +  local j = i
> +  for len=1,1000000000 do
> +    j = bor(band(shr(j,1), band(j,1)-1), band(shl(j,1)+j+1, bnot(band(j,1)-1)))
> +    if cache then
> +      local x = cache[j]; if x then j = x+len; break end
> +    elseif j == 1 then
> +      j = len+1; break
> +    end
> +  end
> +  if cache then cache[i] = j end
> +  if j > m then m, n = j, i end
> +end
> +io.write("Found ", n, " (chain length: ", m, ")\n")
<snipped>
> diff --git a/perf/LuaJIT-benches/ray.lua b/perf/LuaJIT-benches/ray.lua
> new file mode 100644
> index 00000000..2acc24c0
> --- /dev/null
> +++ b/perf/LuaJIT-benches/ray.lua
> @@ -0,0 +1,135 @@
> +local sqrt = math.sqrt
> +local huge = math.huge
> +
> +local delta = 1
> +while delta * delta + 1 ~= 1 do
> +  delta = delta * 0.5
> +end
> +
> +local function length(x, y, z)  return sqrt(x*x + y*y + z*z) end
> +local function vlen(v)          return length(v[1], v[2], v[3]) end
> +local function mul(c, x, y, z)  return c*x, c*y, c*z end
> +local function unitise(x, y, z) return mul(1/length(x, y, z), x, y, z) end
> +local function dot(x1, y1, z1, x2, y2, z2)
> +  return x1*x2 + y1*y2 + z1*z2
> +end
> +
> +local function vsub(a, b)        return a[1] - b[1], a[2] - b[2], a[3] - b[3] end
> +local function vdot(a, b)        return dot(a[1], a[2], a[3], b[1], b[2], b[3]) end
> +
> +
> +local sphere = {}
> +functionsphere:new(centre, radius)
> +  self.__index = self
> +  return setmetatable({centre=centre, radius=radius}, self)
> +end
> +
> +local function sphere_distance(self, origin, dir)
> +  local vx, vy, vz = vsub(self.centre, origin)
> +  local b = dot(vx, vy, vz, dir[1], dir[2], dir[3])
> +  local r = self.radius
> +  local disc = r*r + b*b - vx*vx-vy*vy-vz*vz
> +  if disc < 0 then return huge end
> +  local d = sqrt(disc)
> +  local t2 = b + d
> +  if t2 < 0 then return huge end
> +  local t1 = b - d
> +  return t1 > 0 and t1 or t2
> +end
> +
> +functionsphere:intersect(origin, dir, best)
> +  local lambda = sphere_distance(self, origin, dir)
> +  if lambda < best[1] then
> +    local c = self.centre
> +    best[1] = lambda
> +    local b2 = best[2]
> +    b2[1], b2[2], b2[3] =
> +      unitise(
> +        origin[1] - c[1] + lambda * dir[1],
> +        origin[2] - c[2] + lambda * dir[2],
> +        origin[3] - c[3] + lambda * dir[3])
> +  end
> +end
> +
> +local group = {}
> +functiongroup:new(bound)
> +  self.__index = self
> +  return setmetatable({bound=bound, children={}}, self)
> +end
> +
> +functiongroup:add(s)
> +  self.children[#self.children+1] = s
> +end
> +
> +functiongroup:intersect(origin, dir, best)
> +  local lambda = sphere_distance(self.bound, origin, dir)
> +  if lambda < best[1] then
> +    for _, c in ipairs(self.children) do
> +c:intersect(origin, dir, best)
> +    end
> +  end
> +end
> +
> +local hit = { 0, 0, 0 }
> +local ilight
> +local best = { huge, { 0, 0, 0 } }
> +
> +local function ray_trace(light, camera, dir, scene)
> +  best[1] = huge
> +scene:intersect(camera, dir, best)
> +  local b1 = best[1]
> +  if b1 == huge then return 0 end
> +  local b2 = best[2]
> +  local g = vdot(b2, light)
> +  if g >= 0 then return 0 end
> +  hit[1] = camera[1] + b1*dir[1] + delta*b2[1]
> +  hit[2] = camera[2] + b1*dir[2] + delta*b2[2]
> +  hit[3] = camera[3] + b1*dir[3] + delta*b2[3]
> +  best[1] = huge
> +scene:intersect(hit, ilight, best)
> +  if best[1] == huge then
> +    return -g
> +  else
> +    return 0
> +  end
> +end
> +
> +local function create(level, centre, radius)
> +  local s =sphere:new(centre, radius)
> +  if level == 1 then return s end
> +  local gr =group:new(sphere:new(centre, 3*radius))
> +gr:add(s)
> +  local rn = 3*radius/sqrt(12)
> +  for dz = -1,1,2 do
> +    for dx = -1,1,2 do
> +gr:add(create(level-1, { centre[1] + rn*dx, centre[2] + rn, centre[3] + rn*dz }, radius*0.5))
> +    end
> +  end
> +  return gr
> +end
> +
> +
> +local level, n, ss = tonumber(arg[1]) or 9, tonumber(arg[2]) or 256, 4
> +local iss = 1/ss
> +local gf = 255/(ss*ss)
> +
> +io.write(("P5\n%d %d\n255\n"):format(n, n))
> +local light = { unitise(-1, -3, 2) }
> +ilight = { -light[1], -light[2], -light[3] }
> +local camera = { 0, 0, -4 }
> +local dir = { 0, 0, 0 }
> +
> +local scene = create(level, {0, -1, 0}, 1)
> +
> +for y = n/2-1, -n/2, -1 do
> +  for x = -n/2, n/2-1 do
> +    local g = 0
> +    for d = y, y+.99, iss do
> +      for e = x, x+.99, iss do
> +        dir[1], dir[2], dir[3] = unitise(e, d, n)
> +        g = g + ray_trace(light, camera, dir, scene)
trailing space
> +      end
> +    end
> +    io.write(string.char(math.floor(0.5 + g*gf)))
> +  end
> +end
<snipped>

[-- Attachment #2: Type: text/html, Size: 26606 bytes --]