Re: mathlib

[Coroutines <coroutines@...>]

On Sat, Apr 5, 2014 at 4:44 AM, John Hind <john.hind@zen.co.uk> wrote:

My suggestion on this would be as follows:

1. Decide which functions (or parts of functions) benefit significantly from
being implemented in 'C' (or cannot be implemented in Lua).

2. Implement these in a new API analogous to lua_arith (or just extend
lua_arith).

3. Make a minimal 'C' 'math' library consisting of wrappers round the above
API.

4. Extend this minimal library with standard implementations of the
remaining functions in Lua.

IMHO this should be the pattern for all the libraries: implement in Lua
unless there is a compelling reason for 'C', in which case the functionality
ought to be in the 'C' API as well as the Lua library. For example the
'table' library only needs 'unpack' to be implemented in C and (arguably)
'sort' for performance reasons.

I've never understood why the libraries in the standard Lua distribution
have to be entirely 'C'.

A self-respecting language should "eat its own dogfood" and "take its own
snake-oil"!

On a related note, if table.sort() is in C for performance reasons it might be worth considering changes.  Currently it looks like just quicksort, but it's worth noting that std::sort() in gcc is a hybrid of "introsort" and a linear insertion sort (for when the unsorted area) gets to 16 elements and below.  I can't fathom why they chose something as arbitrary as 16, but that's what it is.  Introsort is a combination of quicksort and heapsort -- heapsort kicks in when the incursion depth of quicksort becomes serious.  I had been working on a new table.sort() that was based on std::sort... Insertion sort is best when the sequence is small, also because it avoids using more memory like quicksort.  The objective was to have O(n log n) running time for the average and worst-case running times, while making use of insertion sort to be light in memory where it made sense to do so.  Here's what I had before I got distracted by other things  (not complete) ~

local swap =

function (self, x, y)

self[x], self[y] = self[y], self[x]

end

local greater_comp =

function (x, y)

return x > y

end

-- {{{ quicksort

-- forward-declare

local qsort = nil

qsort =

function (seq, first, last, gt, depth)

if depth == 0 then error('shiiiiiit nigga') end

if first < last then

local i, p, j = first, first, last

while i < j do

local pivot = seq[p] 

while not gt(seq[i], pivot) do i = i + 1 end

while     gt(seq[j], pivot) do j = j - 1 end

if i < j then

swap(seq, i, j)

end

end

swap(seq, p, j)

depth = depth - 1

qsort(seq, first, j - 1, gt, depth)

qsort(seq, j + 1, last , gt, depth)

end

end

local quicksort =

function (seq, gt, i, j, depth)

i, j  = 1, #seq

gt    = gt    or greater_comp

depth = depth or math.huge

print('>', 'quicksort')

qsort(seq, i, j, gt, depth)

end

-- }}}

-- {{{ heapsort

local left   = function (i) return i * 2             end

local right  = function (i) return i * 2 + 1         end

local parent = function (i) return math.floor(i / 2) end

local build =

function (seq, gt, i, j)

end

-- }}}

-- {{{ introsort

local introsort =

function (seq, gt, i, j)

print('>', 'introsort')

if not pcall(quicksort, seq, gt, i, j, math.log(#seq, 2) * 2) then

heapsort(seq, gt, i, j)

end

end

-- }}}

-- {{{ insertionsort

local insertionsort =

function (seq, gt, i, j)

i  = i  or 1

j  = j  or #seq

gt = gt or greater_comp

print('>', 'insertionsort')

for x = i, j do

local tmp, y = seq[x], x

while y > i and gt(seq[y - 1], tmp) do

seq[y] = seq[y - 1] -- slide up

y      = y - 1

end

seq[y] = tmp

end

end

-- }}}

local tiny_limit = 16

local polysort =

function (seq, gt, i, j)

if (i and j and j - i - 1 <= tiny_limit) or #seq <= tiny_limit then

insertionsort(seq, gt, i, j)

return

end

introsort(seq, gt, i, j)

end