Skip to content

Instantly share code, notes, and snippets.

View appgurueu's full-sized avatar

Lars Müller appgurueu

View GitHub Profile
@appgurueu
appgurueu / bench_mt_rand.lua
Created July 19, 2024 23:55
Minetest random benchmark
collectgarbage"stop" -- we don't want GC heuristics to interfere
local n = 1e8 -- number of runs
local function bench(name, constructor, invokation)
local func = assert(loadstring(([[
local r = %s
for _ = 1, %d do %s end
]]):format(constructor, n, invokation)))
local t = minetest.get_us_time()
func()
@appgurueu
appgurueu / oop_lua.md
Created April 6, 2024 23:21
Object-oriented programming (in Lua)

Object-oriented programming (in Lua)

Time and time again, programming newcomers struggle with grasping the essence of OOP, often confusing it with particularly restrictive implementations. Additionally, Lua newcomers struggle to understand how to implement OOP in Lua, often blindly copying "patterns" and expecting to miraculously obtain whatever they believe is OOP. This is an attempt to clear both up.

Objects

@appgurueu
appgurueu / bench.lua
Created February 8, 2024 20:21
Rudimentary benchmarking of closure-based vs metatable-based OOP in Lua
-- Usage: luajit bench.lua (closures|metatables)
local Foobar = require((...))
for _ = 1, 5 do
local t = os.clock()
local sum = 0
for i = 1, 1e6 do
sum = sum + Foobar("foo", i, "baz"):get_bar()
end
print("dt", os.clock() - t, "sum", sum)
end
@appgurueu
appgurueu / randpairs.lua
Created November 27, 2023 02:13
Randomization of `pairs` traversal order in Lua
--[[
Randomize `pairs` traversal order to deliberately break code that relies on it.
Works by doing a coin toss to decide whether to "postpone" visiting the first entry
(visiting it at the end of the traversal).
Shuffling all keys, then iterating in that shuffled order would provide more thorough randomization; however:
* It is less efficient if the loop is exited early; it may arbitrarily wreck performance
(consider a large table where `pairs` is only used to inspect very few entries.)
* I believe this simple solution already suffices for most code
that incorrectly relies on a specific order of traversal.
Notably, this has a 50% chance of breaking code that
@appgurueu
appgurueu / approx_pi.lua
Created November 15, 2023 18:29
Spreading expensive operations out over multiple server steps using coroutines
local jobs = {}
minetest.register_globalstep(function(dtime)
local remaining_jobs = {}
local time_per_job = dtime / #jobs
for _, job in ipairs(jobs) do
local time_s = minetest.get_us_time() / 1e6
repeat
assert(coroutine.resume(job))
local dtime_s = minetest.get_us_time() / 1e6 - time_s
@appgurueu
appgurueu / lcp.lua
Created August 9, 2023 23:23
Longest common prefix of any two strings in a list of strings
-- Longest common prefix of any two strings in `strs`
local function lcp(strs)
assert(#strs >= 2)
local trie = {}
local max_cp_len = 0
local max_cp_node = trie
for i, str in ipairs(strs) do
local cp_len = 0
local cp_node = trie
while cp_len < #str do
@appgurueu
appgurueu / count_x_inversions.lua
Created June 28, 2023 10:58
Count inversions summing up to `x`
-- Use a modified mergesort to count the inversions summing up to `x`
local function count_x_inversions(
list, -- of distinct nums
x -- target sum
)
local function merge(result, left, right)
local inversions = 0
local i, j, k = 1, 1, 1
local left_idx = {}
for idx, v in ipairs(left) do
import "sort"
// This is not particularly efficient.
// A more efficient implementation might either be B-Tree like,
// might eliminate the index, might distinguish parents and leaves,
// and might strip parents of their values;
// to alleviate the mem management overhead, I'd wish
// for an arena allocator, but this isn't Zig
type PSlice[T any] struct {
@appgurueu
appgurueu / dumpcdb.lua
Created April 11, 2023 18:33
Dump CDB into the current directory using `wget`
#!/usr/bin/env luajit
-- See https://content.minetest.net/help/api/
local http_request = require"http.request"
local lunajson = require"lunajson"
do
-- URI escaping utilities
-- See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/encodeURI
local uri_unescaped_chars = {}
@appgurueu
appgurueu / lua51_vs_luajit_compat.yaml
Last active April 10, 2023 19:08
Lua 5.1 vs LuaJIT Lua 5.2 compatibility semgrep rules
# Rules for programs which must run under both LuaJIT and PUC Lua 5.1
# and which thus may not rely on the 5.2 LuaJIT compatibility features
# See http://luajit.org/extensions.html
rules:
- id: xpcall-args
pattern-either:
# theoretically could be fine e.g. if (empty vararg!), but practically never is
- pattern: xpcall($FN, $ERRHAND, $EXP, ...)
# the following could also theoretically be fine, but practically are a major code smell
- pattern: xpcall($FN1, $FN2(...))