bubbleos VS glibc

do you think writing st is an achievement that merits a turing award

because i've also written a terminal emulator, and it compiles from source in 0.98 seconds https://gitlab.com/kragen/bubbleos/blob/master/yeso/admu-she... screenshot at https://gitlab.com/kragen/bubbleos/blob/master/yeso/admu_she...

(steps to reproduce: install dependencies; make; rm admu-shell admu-shell-fb admu-shell-wercam admu admu.o admu-shell.o admu_tv_typewriter.o; time make -j. it only takes 0.37 seconds if you only make -j admu-shell)

i wrote pretty much all of it on october 12 and 13 of 02018 so forgive me if i don't think that this is an achievement worthy of a turing award. even if it were as great as st

nice! probably magenta on a red background is undesirable, though; maybe switch to colors with better contrasts

i hate x11 visuals and in https://gitlab.com/kragen/bubbleos/blob/master/yeso/yeso-xli... i just assume that everything is 32-bit bgra. i need to get around to fixing that at some point

what do you think an idiomatic ruby binding for yeso would look like? so far i only have lua, c, and python bindings. my ruby experience is both limited (only a few thousand lines of code) and over a decade ago

debian and ubuntu ship an implementation of tetris in the bsdgames package (and bsd has included it since the 80s), gnu emacs has included tetris.el for 25 years (despite removing yow lines), and debian also includes bastet, blocks of the undead, crack-attack, gtkboard, kblocks (which is part of kde), ltris, netris, petris, stax, termtris, tetrinet, tint, vdr-plugin-games, vitetris, /usr/share/vim-scripts/plugin/tetris.vim, and quadrapassel (which is part of the official gnome release)

you've been able to buy cheap '9999 in 1 block game' hardware at any import port with 200 nematic pixels for at least 15 years

i've written two tetris clones myself, http://canonical.org/~kragen/sw/inexorable-misc/tetris and https://gitlab.com/kragen/bubbleos/blob/master/yeso/tetris.c, and no lawsuits have yet arrived

also, minecraft is just an infiniminer clone, and there are fifty zillion clones of each of pacman, space invaders, breakout, snake, doom, and super mario

so these novel legal precedents you mention are at least still being very narrowly applied in practice

since everyone else is posting links to their similar libraries, i thought i'd post mine too, https://gitlab.com/kragen/bubbleos/-/tree/master/yeso

it's probably a bit more efficient than fenster on x-windows because it uses shared memory, and i think the programming interface is a little nicer (see the readme above for code examples)

apps i've written in yeso include an adm-3a terminal emulator, a tetris game, a raytracer, an rpn calculator, a fractal explorer, and so on

i haven't ported yeso to win32/64, macos, android, or the browser canvas yet, just x-windows, the linux framebuffer (partly), and a window system implemented in yeso called wercam

it includes bindings for c, python (via cffi), and lua (via luajit's ffi), and presumably you could use it from zig or rust in the same way as fenster, but i haven't tried

If you're not using derivatives, integrals, or complex numbers, maybe you'd be better off using Wildberger's "rational trigonometry" with quadrances and spreads instead of angles? I haven't actually tried it myself. Wildberger's motivation is a sort of ultra-strict Platonism mixed with the desire to extend analytic geometry to fields other than the real numbers, though, so it wouldn't be surprising if it wasn't actually a simpler way to write Asteroids.

Alternatively you can just directly represent angles as unit vectors in the desired direction, which is pretty much the same as using complex numbers. Angle addition is complex multiplication, angle bisection is complex square root, and computing the sine and cosine is simplicity itself. (This takes twice as much space. If you choose to store only the real part of the complex number, you can only represent angles up to half a turn, same as in Wildberger's approach, you lose some precision near the limits, and the other operations require some extra computations.) I have tried this, for example in http://canonical.org/~kragen/sw/aspmisc/my-very-first-raytra... and https://gitlab.com/kragen/bubbleos/-/blob/master/yeso/sdf.lu..., and in the cases I've tried it, it works great.

I'm interested to hear other people's experiences on this count!

> There at least three small Wasm interpreters in Rust

None of those are small; the smallest one you found is 500 lines of code, and doesn't include the peripherals. The UM interpreter in the Cult of the Bound Variable paper was I think 55 lines of C (also, not including peripherals). My dumb Chifir interpreter was 75 lines of code; adding Yeso graphical output was another 30 lines https://gitlab.com/kragen/bubbleos/blob/master/yeso/chifir-y....

I agree that UM, Chifir, and uxn are Art, and that wasm is a great platform to run this kind of archival virtual machine on top of, as well as having some very interesting ideas about how to design a VM instruction set to be amenable to efficient implementation. RISC-V is a good source of ideas for that, too!

Why am I being so unreasonable about the amount of code? After all, a few hundred lines of C is something that you can write in an afternoon, right, so what's the big deal about 500 lines of code for something you'll use for decades?

The problem is that, to parody Perlis's epigram, if your virtual machine definition has 500 lines of code, you probably forgot some. If a platform includes that much functionality, you have designed it so that that functionality has to live in the base platform rather than being implemented in programs that run on the platform. And that means that you will be strongly tempted to add stuff to the base platform, which is how you break programs that used to work.

In the case of MS-DOS or NES emulation this is limited by the fact that Nintendo couldn't go out and patch all the Famicoms and NESes in people's houses, so if they wanted to change things, well, too bad. NES emulator authors have very little incentive to add new functionality because the existing ROMs won't use it, and that's what they want to run.

One of the interesting ideas in the RISC-V ecosystem is that a Cray-style vector instruction set (RV64V) can give you SIMD-instruction-like performance without SIMD-instruction-like instruction set inflation. And, as the APL family shows, such vector instructions can include scalar math as a special case. I haven't been able to come up with a way to define such a vector instruction set that wouldn't be unacceptably bug-prone, though; https://dercuano.github.io/notes/vector-vm.html describes some of the things I tried that didn't work.

I've written several smaller raytracers than 200 lines of C++, though quite likely they're worse pedagogically than Jaco's slashdotted tutorial:

http://canonical.org/~kragen/sw/aspmisc/my-very-first-raytra... 184 lines of C, including vector arithmetic, input parsing, and PPM output. I'm not sure what you mean by "excluding the headers" — this one doesn't have any headers of its own (why would a 200-line program have headers of its own?) but it #includes math.h, stdio.h, stdlib.h, and string.h, which total almost 1800 lines of code on my machine and presumably 15× that by the time you count their transitive includes.

http://canonical.org/~kragen/sw/dev3/circle.clj 39 lines of Clojure, including the model, which is a single sphere; it uses java.awt.image for JPEG output. About half of the code is implementing basic vector math by hand. A minified version is under 1K: http://canonical.org/~kragen/sw/dev3/raytracer1k.clj

https://gitlab.com/kragen/bubbleos/blob/master/yeso/sdf.lua 51 lines of Lua for an SDF raymarcher including animation, the model itself, and live graphical output.

I feel like basic raytracing is a little simpler than basic rasterizing, but I don't think the difference is hugely dramatic:

http://canonical.org/~kragen/sw/torus is a basic rasterizer in 261 lines of JS, which is larger than the three raytracers I mentioned above, but about 60% of that is 3-D modeling rather than rendering, and another 5% or so is DOM manipulation.

http://canonical.org/~kragen/sw/netbook-misc-devel/rotcube.p... The smallest I've been able to get a basic rasterizer down to, 15 lines of Python, just rotating a point cloud.

http://canonical.org/~kragen/sw/dev3/rotcube.cpp in C++ it's 41 lines, and

http://canonical.org/~kragen/sw/dev3/braillecube.py with wireframes in Braille Unicode art it's 24 lines of Python.

So I think that the core of either a (polygon!) rasterizer or a raytracer, without optimizations, is only about 20 lines of code if your ecosystem provides you with the stuff around the edges: graphical display (or image file output), model input, linear algebra, color arithmetic.

For a rasterizer, it's something like:

    tpoints = [camera_transform @ point for point in points]

https://gitlab.com/kragen/bubbleos/blob/master/yeso/sdf.lua one page of Lua, runs in real time at a lousy framerate

http://canonical.org/~kragen/sw/dev3/ about five pages of C

I wonder if you’re using a different definition of ‘vectorized’ from the one I would use. For example glibc provides a vectorized strlen. Here is the sse version: https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/m...

It’s pretty simple to imagine how to write an unoptimized version: read a vector from the start of the string, compare it to 0, convert that to a bitvector, test for equal to zero, then loop or clz and finish.

I would call this vectorized because it operates on 16 bytes (sse) at a time.

There are a few issues:

1. You’re still spending a lot of time in the scalar code checking loop conditions.

2. You’re doing unaligned reads which are slower on old processors

3. You may read across a cache line forcing you to pull a second line into cache even if the string ends before then.

4. You may read across a page boundary which could cause a segfault if the next page is not accessible

So the fixes are to do 64-byte (ie cache line) aligned accesses which also means page-aligned (so you won’t read from a page until you know the string doesn’t end in the previous page). That deals with alignment problems. You read four vector registers at a time but this doesn’t really cost much more if the string is shorter as it all comes from one cache line. Another trick in the linked code is that it first finds the cache line by reading the first 16 bytes then merging in the next 3 groups with unsigned-min, so it only requires one test against a zero vector instead of 4. Then it finds the zero in the cache line. You need to do a bit of work in the first iteration to become aligned. With AVX, you can use mask registers on reads to handle that first step instead.

That was also my thought. To my knowledge `/etc/localtime` is the creation of Arthur David Olson, the founder of the tz database (now maintained by IANA), but his code never read `/etc/localtime` multiple times unless `TZ` environment variable was changed. Tzcode made into glibc but Ulrich Drepper changed it to not cache `/etc/localtime` when `TZ` is unset [1]; I wasn't able to locate the exact rationale, given that the commit was very ancient (1996-12) and no mailing list archive is available for this time period.

[1] https://github.com/bminor/glibc/commit/68dbb3a69e78e24a778c6...

That's not really what the problem is. The actual code is fine.

The issue is that the definition of `fd_set` has a constant size [1]. If you allocate the memory yourself, the select() system call will work with as many file descriptors as you care to pass to it. You can see that both glibc [2] and the kernel [3] support arbitrarily large arrays.

[1] https://github.com/bminor/glibc/blob/master/misc/sys/select....

[2] https://github.com/bminor/glibc/blob/master/sysdeps/unix/sys...

[3] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

The source code for that is here.

Expanding macro gives three GCC function attributes [2]: `__attribute__ ((malloc))`, `__attribute__ ((alloc_size(1)))` and `__attribute__ ((warn_unused_result))`. They are required for GCC (and others recognizing them) to actually ensure that they behave as the standard dictates. Your own malloc-like functions won't be treated same unless you give similar attributes.

[1] https://github.com/bminor/glibc/blob/807690610916df8aef17cd1...

[2] https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...

IFunc relocations is what enables glibc to dynamically choose the best memcpy routine to use at runtime based on the CPU.

see https://github.com/bminor/glibc/blob/glibc-2.31/sysdeps/x86_...

memmove can be very well implemented in pure C, libc implementations usually have a "generic" (meaning, architecture independent) fallback. Here is musl generic implementation and its x86-64 assembly implementation. For glibc, implementation is a bit more complex, having multiple architectures implemented, but you could find a generic implementation with these two files: memmove.c and generic/memcopy.h.

Yeah, looks like the Q_strcat(pszContentPath, "/"); is invalid, as glibc has only allocated exactly enough to fit the path in the buffer returned by realpath().

Interestingly, the open group spec says that a null argument to realpath is "Implementation defined" [0]

And the linux (glibc) man pages say it allocates a buffer "Up to PATH_MAX" [1]

I guess "strlen(path)" is "Up to PATH_MAX", but the man page seems unclear - you could read that as implying the buffer is always allocated to PATH_MAX size, but that's not what seems to be happening, just effectively calling strdup() [2]. I have no idea how to feed back to the linux man pages, but might be worth clarifying there.

[0] https://pubs.opengroup.org/onlinepubs/009696799/functions/re...

[1] https://linux.die.net/man/3/realpath

[2] https://github.com/bminor/glibc/blob/0b9d2d4a76508fdcbd9f421...

For the actual sources you will have to look at one of the mirrors of the C standard library, such as https://github.com/bminor/glibc/tree/master/sysdeps/ieee754/dbl-64