1brc in SPITBOL

[CheyenneWills]

I was wondering how well SPITBOL (an implementation of SNOBOL) would do.

The only real optimization done was using integer arithmetic by first multiplying the temperature by 10 and then "formatting" the values.

SPITBOL (SNOBOL) doesn't support theads, it handles it's own storage management, and uses dynamic data typing.

      &trim = 1
      &stlimit = 0

      define('fmt(v)x,d')
      data('tempdata(min,max,mean,total)')

      stations = table(10000)
      input(.in,10, 'measurements.txt')

* Pattern to parse the input
      stationpat = breakx(';') . station ';' rem . temp

loop  line = in                                           :f(done)
      line stationpat                                     :f(error)

* Do all the arithmetic as integers
      temp = convert(convert(temp,'real') * 10, 'integer') 

* First time seeing this station.. set initial values
      stations[station] = ident(stations[station])
+                         tempdata(temp, temp, 1, temp)   :s(loop)

* Otherwise update the existing entry
      v = stations[station]
      mean(v) = mean(v) + 1
      min(v) = lt(temp, min(v)) temp
      max(v) = gt(temp, max(v)) temp
      total(v) = total(v) + temp                          :(loop)

done  stations = sort(stations)
      i = 0
      outstr = ''
report
      station = stations[i = i + 1,1]                     :f(finish)
      v = stations[i,2]
      outstr = outstr ',' station '=' 
+              fmt(min(v)) '/' 
+              fmt(total(v) / mean(v)) '/' 
+              fmt(max(v))                                :(report)
   
finish output = '{' substr(outstr,2,size(outstr) - 1) '}' :(end)

error output = 'error reading line:' line

* A little cheat to format a value as a real with a single digit decimal.
fmt   fmt = convert(v,'string')
      fmt len(size(v) - 1) . x rem . d = x '.' d          :(return) 
end

Intel Xeon 3.4Ghz 4 core

time spitbol -x -i256m -d512m ./1brc.spt
...
normal end
in file              ./1brc.spt
in line              48
in statement         39
stmts executed       9000002080
execution time msec  578919
stmt / microsec      15
stmt / millisec      15546
stmt / second        15546000
regenerations        669
memory used (bytes)  30824480
memory left (bytes)  237610968


real	9m43.523s
user	9m31.442s
sys	0m7.503s

For reference:

./calculate_average_baseline.sh
real	4m5.039s
user	3m59.073s
sys	0m5.393s

[rrcook]

That's impressive for a single-threaded, dynamically typed language. Is SPITBOL generally a fast language?

[CheyenneWills]

SPITBOL is a "compiled" version of SNOBOL, and was designed to be very efficient and fast

SPITBOL itself is written in a pseudo assembly language called minimal. There is a minimal -> x86_64 nasm "assembler"

Digging into the innards, it's more of a JIT implementation

Basically, SPITBOL takes a statement during the "compile" phase and creates a list of internal code blocks that perform the individual operations -- using some kind-of-C it looks like:

struct cdblk {
  ptr-to-routine execute-statement;
  .. a bunch of house keeping stuff for this statement ..
   ptr-to-routine failure_exit;
   ptr-to-routine codewords[];
}

The "execute-statement" looks something like:

   cur_codeword = 0;
   goto codewords[ cur_codeword ];

And then the individual routines look something like:

xxx
...do whatever the operations is...
goto codewords[ ++cur_codeword ];

So given the statement:
B = A + 1

The codewords for this statement would be a bunch of "pointers" to static code

  A_vblk_push_value      -- Pushes the value in variable A
  const_X_push_value    -- Pushes a constant value
  add_op                         -- adds the top 2 values in the stack, pushes the result
  B_vblk_push_name     -- Target for the assign
  assign_op                    -- assigns the 2nd value on stack to the variable that is on the top of the stack
  next_statement             -- go process the next statement

So a "_vlk" is a variable block, which contains an internal pointer to the code that "knows" how to get a value, or assign a value to that variable, etc.

Here is the actual code for implementation for the addition operation (in nasm)

o_add:                                          ; 
        call arith                              ; fetch arithmetic operands} jsr arith  
        dec  m_word [_rc_]                      ; 
        js   call_5                             ; 
        dec  m_word [_rc_]                      ; } err 001 addition left operand is not numeric 
        jns  _l0008                             ; 
        mov  m_word [_rc_],1                    ; 
        jmp  err_                               ; 
_l0008:                                         ; 
        dec  m_word [_rc_]                      ; } err 002 addition right operand is not numeric 
        jns  _l0009                             ; 
        mov  m_word [_rc_],2                    ; 
        jmp  err_                               ; 
_l0009:                                         ; 
        dec  m_word [_rc_]                      ; jump if real operands} ppm oadd1  
        jns  _l0010                             ; 
        jmp  oadd1                              ; 
_l0010:                                         ; 
call_5:                                         ; 
        add  ia,m_word [(cfp_b*icval)+xl]       ; add right operand to left} adi icval(xl)  
        jno  exint                              ; return integer if no overflow} ino exint  
        mov  m_word [_rc_],3                    ; } erb 003 addition caused integer overflow 
        jmp  err_                               ; 
oadd1:
        ldmxcsr [mxcsr_set]                     ; add right operand to left} adr rcval(xl)  
        addsd ra,[(cfp_b*rcval)+xl]             ; 
        stmxcsr [mxcsr]                         ; 
        test m_word [mxcsr],0x0010              ; 
        jz   _l0011                             ; 
        pxor ra,ra                              ; 
        ldmxcsr [mxcsr_set]                     ; 
_l0011:                                         ; 
        call do_chk_real_inf                    ; return real if no overflow} rno exrea  
        jz   exrea                              ; 
        mov  m_word [_rc_],261                  ; } erb 261 addition caused real overflow 
        jmp  err_                               ; 
...
exint:
        xor  xl,xl                              ; clear dud value} zer xl  
        call icbld                              ; build icblk} jsr icbld  
exixr:
        push xr                                 ; stack result} mov -(xs) xr 
exits:
        mov  r10,m_word [r13]                   ; load next code word} lcw xr  
        mov  xr,r10                             ; 
        add  r13,cfp_b                          ; 
        mov  xl,m_word [xr]                     ; load entry address} mov xl (xr) 
        jmp  xl                                 ; jump to execute next code word} bri xl  

err_: ...

[rrcook]

Wow, thank you for the detailed explanation, I wasn't expecting that much.
9 minutes isn't bad for a solution that has to be single-threaded.
Looks like there's a whole interesting ecosystem build around SPITBOL, I'll have to take a look.

[CheyenneWills]

SNOBOL is the language, while SPITBOL is just a specific implementation of SNOBOL.

The original implementation of SNOBOL was written it's own specific "virtual machine" assembly language, called "SIL" -- SNOBOL Implementation Language. A good start is to review the Wikipedia entry for SNOBOL. And a good resource is Phil Budne's page -> https://www.regressive.org/snobol4/ (the snobol4.org domain was "lost" unfortunately). Phil's CSNOBOL is an interesting implementation, Phil took the original SIL implementation and used C as the backend language. The CSNOBOL is probably has the most features for the language. Another SIL implementation is Viktors Berstis's http://snobol5.org/

I recently took over the maintenance of the SPITBOL implementation and have been working on cleaning it up.