I THINK ∴ I'M DANGEROUS

BFE NOTES

Locks

It would seem my locking procs (flock, funlock) do not work quite as well as I had hoped. They do not appear to be atomic and I also believe them to be the cause of the random lockups.

I will most likely need to implement an actual file locking mechanism

Solution

I cheated and just wrote some wrapper procs that use flock(1) and shell scripts.

Addendum:

BFE seems to still be murdering my fileserver. I think my next solution will involving switch from file-based to sqlite3-based.

Addendeum 2:

sqlite3 uses the same damn locking mechanism as flock. It is especially known to be troublesome on NFS. So I wrote a wrapper to make an sqlite network server.

Queues

The queues seem to work best when simply operating at full capacity. Workers should just fill and drain as able. The vast majority of CPU time is spent testing programs, so there's really no waste in letting one worker completely fill the mutate and evaluate queues.

NMC RA

There seems to be some sort of corner case with nmc_ra_files leading to a segfault / double free. I need to investigate that.

UBI4 EOF

The way ubi4 handles EOF is a bit of an issue. The interpreter needs to handle dealing with zeroes as valid input but also needs to be able to 'know' when to stop reading input.

Solution(s ?)

  • Exit if a byte is read and EOF is returned
    • Seems like this would make it much harder for my initial test to work
  • Increase cell size for bytes to ints, use extra storage to handle special conditions such as -1 to mean EOF (I do not like this. It breaks byte-cell wrapping, and will decrease performance)
  • Fall back to removing the read and write commands and simply load the input onto the sheet and read the results afterwards
    • Problems with this include no allowance for temp space / scratch data must be cleaned up before the program exits
  • Ignore it
    • See how far I can get–is this really a problem?

Strand Similarity and Cell Wrapping

It occurred to me that because ubi4 does cell value wrapping (i.e. 255 + 1 = 0; 0 - 1 = 255) that cells with the value 255 are really only 1 away from zero, but n-Depth Mean Compare will calcuate the distance to be 254.

How would that math work?

If the difference between to values is less than 128, than that is the difference.

If the difference is greater than 128, there's a shorter path via cell wrapping. This cell-wrapped difference can be calculated via

` 256 - |A - B| `

And this can be dropped into the C code for where the difference is calculated:

d = fabs ( nmc_mean_c ( s1 + i*s1_chunk, s1_chunk ) - nmc_mean_c ( s2 + i*s2_chunk, s2_chunk ) );
diffs[i] = d < 128 ? d : 256 - d;

Halting Problem / Infinite loops

Ah, the good ol' halting problem. How to know (externally) if an algorithm is “done” or stuck in an infinite, unproductive loop. In my super fast BF interpreter, I was able to successfully determine if I were stuck in an infinite loop and exit. This was done from within the interpreter itself, so no, I am not claiming to have solved the Halting Problem.

The problem is that the infinite loop detection adds so much overhead, it's useless. Even with a few tweaks, it's still useless. So I think the only way around the halting problem is some sort of timeout, which I find such an ugly and unpalatable solution.

Putting a Cheetah in an Elephant

I wrote (inspired by someone else, granted) a very very fast BF interpreter. BF code is preprocessed into a linked list. Loops are intelligently processed recursively. It's fast and beautiful in its simplicity. The speed comes from its simplicity and pretty direct mapping of bf to C and thus pretty direct mapping from BF to actual machine language. There's a few optimizations built in as well (such as knowing [-] is the same as *cell = 0).

The question is, how do I make this C program play well with the Evolution framework, which will be written in Tcl?

Here's all the options I'm aware of:

  • C Tcl Extension
  • Executable Module
  • FFIDL - Tcl Extension to allow direct access of C library Functions from Tcl
  • SWIG - Tool to adapt a C library into a Tcl extension
  • Critcl - Run compile and run C-code on the fly from within Tcl

I'm leaning towards critcl. The plan is to keep all the C stuff self-contained and only expose 1 C function to tcl: bfrun which would take two parameters, bfcode and bfinput.

Built into the exposed bfrun would be timeout and error detection.

Implementation

I ended up going with an executable module. This has several benefits, not the least of which is ease of implementation. The other benefit is I can just the thing segfault and it counts as a failed run, thus saving me processing time on bounds checking.