Liberation through Computer Literacy

[Paeryn]

Well, if your language does not allow you to read via an uninitialized pointer, if it does not allow the creation of null pointers, if it does not allow you to point at the wrong thing, if it does not allow you to share pointers for write operations, then there is no need for pointer checking at run time. You cannot create a rogue pointer in the first place.

Yes, I can see that.
But what about a function in a separate TU, a separately compiled and linked module, maybe a public library function.

The function has been been presented with a "char *" as an input parameter. It must do all those checks by hand to ensure a crash free experience? Or perhaps the function body is declared "unsafe". Or perhaps rustc/cargo or whatever it is, expects to manage the entire project including all the libraries. Uuugh.

Rust likes to create static programs, by default all the crates (libraries) your program uses are statically linked so it knows exactly what the crates are doing.

Dynamic libraries require trust so foreign libraries can only be called from unsafe blocks, usually in a rust wrapper library, this allows for the minimum amount of unsafe code, just enough to make the call and convert any data. Obviously if the foreign function returns a char* for example, rust has to assume that the pointer is valid, the wrapper function should create the appropriate rust type and initialise it accordingly. That way rust can keep its guarantee that its code is valid.

Or take the simple library function strcpy(), does it also get passed the lengths of both argument strings? Otherwise how can it do the bounds check? Perhaps it avoids that sort of thing, by including small string handling stuff within the language itself.

Rust's String type is essentially a struct containing a pointer to allocated memory, an integer saying how much memory is allocated and an integer saying how long the current string stored there is. Strings are also utf-8, you can make a String from a raw u8 array but doing so is marked unsafe as it can't guarantee that invalid characters aren't used.

[ejolson]

That aluminium case for the Pi 4B certainly looks nice. Given my budget, I suspect a different solution will present itself that involves scavenging heatsinks from surplus motherboards. More details as things develop.

The wicked case is expensive and that level of cooling is not needed. Its kind of nice though if you don't use WiFi, the Pi is encased in a heavy machined aluminum block.

I suggest not bothering with any additional cooling at first. Leave it out of a case in free air, preferably on edge, and monitor for throttling with "vcgencmd get_throttled" after a typical workload.

My Pi 4B is now unpacked, mounted vertically and running off the official power supply. There are no aftermarket heat sinks attached, but since I had a fan on the same shelf, it is now pointing toward the Pi. I've run a few light-weight tests and so far vcgencmd reports no throttling. It looks like the perfect computer to end the digital apocalypse and begin an age of liberation through computer literacy.



The zombie's parallel C code now runs in less than a quarter of a second and I'm currently thinking how to make the new insane British anagram bar chart of fame.

[Heater]

That looks great. You have built a Turbo Encabulator:
http://www.rfcafe.com/miscellany/humor/ ... ulator.pdf

[ejolson]

That looks great.

Preliminary results are now in for the Pi 4B version of the Insane British Anagram Bar Chart of Fame.



The colors got mixed up, but I've left them that way because the change helps distinguish the new chart from the Pi 3B+ original. Edit: It looks like the original chart changed as well when I regenerated it. The change must be related to a different version of R on Buster.

I'm missing the code for the GMP version of the prime hash discussed here. If you post it, I would run it on the Pi 4B. Edit: the code has been posted, executed and added to these files used to make the bar chart. Also note that I have not rerun the ScriptBasic code anagram-sb.bas which uses O(n) associative arrays and have instead repeated the previously reported timing which was made on a fairly modern x86 compatible computer. Edit: The entry for anagram-sb.bas has now been updated with timings for the Pi 4B.

As mentioned before, the speed of execution is a secondary compared with demonstrating programming techniques and algorithms that build computer literacy and, of course, get the correct answer. Additional solutions to the anagram challenge would be wonderful.

[Heater]

ejsolson,

Great your Turboencabulator is working well.

At 0.637s it's running v3 of my Rust twice as fast as my latest effort on a Pi 3 at 1.457s. And nearly as fast at it runs on my PC at 0.580s.

My C++ solution using GMP for the prime hash is this:

Code: Select all

//
// insane-british-anagram-gmp.cpp - Find words that have valid anagrams
//                                  Words sourced from Debian's british-english-insane dictionary
//
// heater - 2019-07-28
// 
#include <fstream>
#include <string>
#include <stdlib.h>
#include <string.h>
#include <unordered_map> 
#include <vector> 
#include <cassert> 
#include <iostream> 
#include <gmpxx.h>

// GMP does not have a hash function so we create one for it.
struct GMPHash {
std::size_t operator()(const mpz_class& k) const
    {
        const std::string s = k.get_str (10);
        return std::hash<std::string>()(s);
    }
};

std::string getFileContents(const char *filename) {
    std::ifstream in(filename, std::ios::in | std::ios::binary);
    if (in) {
        std::string contents;
        in.seekg(0, std::ios::end);
        contents.resize(in.tellg());
        in.seekg(0, std::ios::beg);
        in.read(&contents[0], contents.size());
        in.close();
        return(contents);
    }
    throw(std::runtime_error("Shit happened!"));
}

mpz_class primeHash (const char* const word) {
    // One prime number for each lower case letter of the alphabet
    std::vector<mpz_class> primes {
        7, 61, 29, 41,
        2, 67, 53, 47,
        3, 101, 73, 23,
        43, 11, 13, 37,
        97, 17, 5, 19,
        31, 71, 79, 83,
        59, 89
    };

    mpz_class hash(1);
    const size_t len = strlen(word);
    for (size_t i = 0; i < len; i++) {
        int index = word[i] -  97;
        hash = hash * primes[index];
    }
    return hash;
}

int main (int argc, char* argv[]) {
    // Map container for sets of anagrams 
    // An anagram set is simply a vector of pointers to words in the dictionary
    // Keys for the anagram sets in the map are the ordered characters of the words.
    std::unordered_map<mpz_class, std::vector<char*>, GMPHash> anagramMap;

    // An ordered index of anagram set keys 
    std::vector<mpz_class> index;

    auto dictionary = getFileContents("/usr/share/dict/british-english-insane");
    char* dictionaryPtr = (char*)dictionary.c_str();
    char* wordPtr = dictionaryPtr;
    char* charPtr = wordPtr;
    bool reject = false;
    while (1) {
        if (islower(*charPtr)) {
            // We are scanning a valid word
            charPtr++;
        } else if ((*charPtr) == '\n') {
            // We have hit the end of a word, use the word if it's valid
            *charPtr = 0;
            if (!reject) {
                // Do we have a word with this key (potential anagram)?
                mpz_class key = primeHash(wordPtr);

                auto it = anagramMap.find(key);
                if (it == anagramMap.end()) {
                    // No: Add it to the map as start of new anagram set.
                    anagramMap[key].push_back(wordPtr);

                    // And add the new anagram set to index
                    index.push_back(key);
                } else {
                    // Yes: Append it to the existing anagram set.
                    it->second.push_back(wordPtr); 
                }
            }
            charPtr++;
            wordPtr = charPtr;
            reject = false;
        } else if ((*charPtr) != 0) {
            // Invalid character
            reject = true;
            charPtr++;
        } else {
            // End of dictionary
            break;
        }
    }

    // Iterate over the collected anagram sets in order of the index.
    for(auto const& key: index) {
        auto it = anagramMap.find(key);
        if (it->second.size() > 1) {
            int count = 0;
            for(const auto& value: it->second) {
                if (count == 1) {
                    fputs(": ", stdout);                
                } else if (count > 1) {
                    fputs(", ", stdout);                
                }
                fputs(value, stdout);                
                count++;
            }
            fputs("\n", stdout);                
        }
    }
    return (0);
}

Don't forget to clean the flux ports on the encabulator's entropy distributor once a week so as to avoid any terminal reaction vessel meltdown.

[ejolson]

Great your Turboencabulator is working well.

At 0.637s it's running v3 of my Rust twice as fast as my latest effort on a Pi 3 at 1.457s. And nearly as fast at it runs on my PC at 0.580s.

My C++ solution using GMP for the prime hash

Thanks! I now have a name for the new Pi. Since turboencabulator is a bit too long, I shortened it to turbo. Next, I need to go to the (grocery) store and find a proper casing for the parametric wind tunnel to channel the turbulence generated by the entropy distributor towards the central processing unit.

Results of the GMP code are

Code: Select all

$ g++ -mcpu=cortex-a7 -mfpu=neon-vfpv4 -ffast-math -O3 -o iba-gmp iba-gmp.cpp -lm -lgmp
$ time ./iba-gmp >iba-gmp.insane

real    0m4.248s
user    0m4.118s
sys 0m0.130s
$ time ./iba-gmp >iba-gmp.insane

real    0m4.173s
user    0m4.052s
sys 0m0.120s
$ time ./iba-gmp >iba-gmp.insane

real    0m4.271s
user    0m4.129s
sys 0m0.140s
$ md5sum iba-gmp.insane selfgrams.pl.insane 
addeda36a4631afc983f3bff13742e36  iba-gmp.insane
addeda36a4631afc983f3bff13742e36  selfgrams.pl.insane

I've updated the Insane British Anagram Bar Chart of Fame.

Since cream rises to the top, it's not surprising that Basic has taken over the top of the bar chart. As Basic was the language responsible for the widespread computer literacy of the golden age of personal computing, I've been looking at hanagram.bas to see if there are any obvious ways to improve the performance. I've also discovered Visual Basic has a built-in dictionary type that should allow for a straight-forward translation of the Script Basic program.

I'm tempted to write an O(n^2) code in C to determine whether the choice of language or algorithm is responsible for the observed global warming. I asked the lead developer of FidoBasic who whined, there's more than one way to skin a cat. I suspect n-level meta programming makes things even slower.

I wonder whether Haskell is more like milk or more like cream.

[Heater]

Since the cream is supposed to rise to the top your chart must be upside down

[John_Spikowski]

VB doen't run on the RPi so would it still count?

[ejolson]

VB doen't run on the RPi so would it still count?

Visual Basic .NET runs on the Raspberry Pi using Mono and the open-source vbnc compiler.

[gkreidl]

Just for completeness I have also tested other algorithms in Python but they were all slower than the method using ordered strings.

Here is the version using ordered prime numbers (selfgrams_prime.py). It might be interesting to see how it performs RPi 4 running Buster.
#!/usr/bin/python3

import sys,re

Code: Select all

if sys.version[0:3] < "3.6":
    from collections import OrderedDict
    anagrams = OrderedDict()
else:
    anagrams = {}

hashd = {'a':7,'b':61,'c':29,'d':41,'e':2,'f':67,'g':53,'h':47,'i':3,'j':101,'k':73,'l':23,'m':43,'n':11,'o':13,'p':37,'q':97,'r':17,'s':5,'t':19,'u':31,'v':71,'w':79,'x':83,'y':59,'z':89}

f = open('/usr/share/dict/british-english-insane','rt')
dictionary = f.read().split('\n')
f.close()

check = re.compile('^[a-z]+$')

for word in dictionary:
    if check.match(word):
        keyl = list(word)
        key = 1
        for ch in keyl:
            key *= hashd[ch]
        if key in anagrams:
            anagrams[key].append(word)
        else:
            anagrams[key] = [word]

output = ''
for v in anagrams.values():
    if len(v) > 1:
        op = ', '.join(v) + '\n'
        output += op.replace(',',':',1)
print(output,end='')

BTW, using GMP (via gmpy2) does not speed it up, because for such "small" BITGINTs the built-in method is at least not slower.

[ejolson]

Just for completeness I have also tested other algorithms in Python but they were all slower than the method using ordered strings.

Here is the version using ordered prime numbers (selfgrams_prime.py). It might be interesting to see how it performs RPi 4 running Buster.

Fantastic! Another bar to add to the chart! The results on the Pi 4B are

Code: Select all

$ python3 --version
Python 3.7.3
$ time ./selfprime.py >selfprime-py.insane 

real    0m5.260s
user    0m5.026s
sys 0m0.231s
$ time ./selfprime.py >selfprime-py.insane 

real    0m5.202s
user    0m4.941s
sys 0m0.261s
$ time ./selfprime.py >selfprime-py.insane 

real    0m5.508s
user    0m5.307s
sys 0m0.201s
$ md5sum selfprime-py.insane selfgrams.pl.insane 
addeda36a4631afc983f3bff13742e36  selfprime-py.insane
addeda36a4631afc983f3bff13742e36  selfgrams.pl.insane

I also ran the code on the Pi 3B+ for comparison and obtained

Code: Select all

$ python3 --version
Python 3.5.3
$ time ./selfprime.py >selfprime-py.insane

real    0m16.724s
user    0m16.576s
sys 0m0.140s
$ time ./selfprime.py >selfprime-py.insane

real    0m17.009s
user    0m16.886s
sys 0m0.120s
$ time ./selfprime.py >selfprime-py.insane

real    0m16.599s
user    0m16.471s
sys 0m0.120s

The 3-fold improvement is amazing. I wonder if the differences are more than just improved hardware. The Pi 4B is also running a newer version of Python. The bar charts have been updated with both results.

[PeterO]

That looks great. You have built a Turbo Encabulator:
http://www.rfcafe.com/miscellany/humor/ ... ulator.pdf

https://www.youtube.com/watch?v=Ac7G7xOG2Ag

PeterO

[ejolson]

Since the cream is supposed to rise to the top your chart must be upside down

I just got a letter from the zombies which read

Our zanagram.c program is 100% fat free. For more information let us in now.

I tried turning the chart rightside up, but every time the screen on my phone shifted and turned it upside down again. I fear that the digital apocalypse is near.

[Heater]

bensimmo,

I really want a browser based solution to sit alongside the prime one, so I can test on various devices.

OK. Just for you. Insane British Anagrams found in your browser from a downloaded dictionary.
http://otaniemi.conveqs.fi:9000/www/

Created from the Rust solution, insane-british-anagram-4.rs, compiled to WEB assembly with rustc/cargo and bound to Javascript with wasm-bindgen.

With the amazing result that it runs nearly as fast as my original C++ solution compiled to native x86-64 !

I'll leave it as an exercise to the reader to check the result is correct.

[ejolson]

bensimmo,

I really want a browser based solution to sit alongside the prime one, so I can test on various devices.

OK. Just for you. Insane British Anagrams found in your browser from a downloaded dictionary.
http://otaniemi.conveqs.fi:9000/www/

That's quite impressive. While I didn't check every anagram, it's clearly insane because the last word on the list is zoogrpahy.

With my phone I obtain

Insane British Anagram
(Using Rust and WASM)

This page finds all the anagrams in the british-english-insane dictionary as found in Debian.

Dowloading dictionary... OK
Finding anagrams... OK
WASM execution time: 4372 milliseconds.

Did you install the insane dictionary for your spell checker?

[Heater]

Pretty good. Takes nearly 10 seconds on my old phone.

Speeling fiksed.

[Paeryn]

Not bad for the Rust/WASM version, my Galaxy S9 runs it in 1189 milliseconds. I must get around to fixing my Haskell version.

[Heater]

Just now I'm having a hard time believing what I am seeing.

When I run the insane-british-anagram in the web browser on my PC I see an execution time like so:

Code: Select all

WASM execution time: 415 milliseconds.

Now, that is timed in Javascript and is the time taken to find anagrams in the dictionary, which is just a long JS string at that point. It does not include the time taken to fetch that string from the server or output the result to the page.

So I added some timing to the program to show the same execution time when run as native x86-64 code. Excluding time taken to read the dictionary file or print the result.

Code: Select all

$ time ./target/release/insane-british-anagram > temp.txt
501ms

real    0m0.551s
user    0m0.141s
sys     0m0.391s
$ md5sum temp.txt
addeda36a4631afc983f3bff13742e36  temp.txt

WTF?

Yes, running Rust compiled to WASM and interpreting it in the browser is faster than compiling to native code and having the CPU run it directly! By a huge margin, almost 20%.

Am I going nuts? This cannot be...

[ejolson]

Am I going nuts? This cannot be...

Could it be that the clock functions in web assembler are intentionally inaccurate as part of a mitigation for some famous timing-based side-channel attacks?

[ejolson]

Since cream rises to the top, it's not surprising that Basic has taken over the top of the bar chart. As Basic was the language responsible for the widespread computer literacy of the golden age of personal computing, I've been looking at hanagram.bas to see if there are any obvious ways to improve the performance.

After a few micro-optimizations to hanagram.bas I arrived at

Code: Select all

1000 REM hanav2.bas -- Find anagrams
1010 REM Written July 24, 2019 by Eric Olson
1020 REM
1030 REM This program demonstrates using letter counts and a heap to
1040 REM find anagrams in the insane British dictionary.
1050 REM
1060 DEFLNG A-Z
2000 F$="/usr/share/dict/british-english-insane"
2001 REM F$="tail.dat"
2010 M0=0:OPEN F$ FOR INPUT AS #1
2015 IF EOF(1)<>0 THEN 2030
2020 INPUT #1,A$:M0=M0+1:GOTO 2015
2030 DIM L$(M0),K$(M0),H(M0),V0(26)
2040 CLOSE #1:OPEN F$ FOR INPUT AS #1
2050 A1=ASC("a")-1:A2=ASC("0"):N0=0:H0=0
2060 FOR I=1 TO M0:INPUT #1,A$
2063 FOR J=1 TO 26:V0(J)=0:NEXT J:J=0
2065 IF J>=LEN(A$) THEN 2075
2068 J=J+1:C=ASC(MID$(A$,J,1))-A1
2070 IF (C<1) OR (C>26) THEN 2130
2071 V0(C)=V0(C)+1:GOTO 2065
2075 V$="00000000000000000000000000":FOR J=1 TO 26
2080 MID$(V$,J,1)=CHR$(V0(J)+A2):NEXT J
2120 N0=N0+1:L$(N0)=A$:K$(N0)=V$:GOSUB 4000
2130 NEXT I:CLOSE #1
2140 IF H0=0 THEN 9000
2150 GOSUB 4500
2160 J0=J:L$(J0)=L$(J0)+":"
2170 IF H0=0 THEN 2400 
2180 GOSUB 4500
2190 IF K$(J)<>K$(J0) THEN 2160
2200 L$(J0)=L$(J0)+" "+L$(J)+",":GOTO 2170
2400 FOR I=1 TO N0:A$=L$(I)
2410 IF RIGHT$(A$,1)<>"," THEN 2430
2420 PRINT LEFT$(A$,LEN(A$)-1)
2430 NEXT I
2900 GOTO 9000
4000 REM Insert a key into the heap
4010 REM  inputs: N0 the key to insert
4020 H0=H0+1:R=H0:H(R)=N0
4030 S=INT(R/2):IF S=0 THEN RETURN
4035 IF K$(H(R))>K$(H(S)) THEN RETURN
4036 IF K$(H(R))<K$(H(S)) THEN 4060
4040 IF L$(H(R))>=L$(H(S)) THEN RETURN
4060 T=H(S):H(S)=H(R):H(R)=T:R=S:GOTO 4030
4500 REM Remove a key from the heap
4510 REM  output: J the key removed
4520 J=H(1):H(1)=H(H0):H0=H0-1:S=1
4530 R0=2*S:R1=R0+1:IF R0>H0 THEN RETURN
4535 IF R1>H0 THEN 4550
4536 IF K$(H(R0))>K$(H(R1)) THEN 4600
4537 IF K$(H(R0))<K$(H(R1)) THEN 4550
4540 IF L$(H(R0))>=L$(H(R1)) THEN 4600
4550 IF K$(H(R0))>K$(H(S)) THEN RETURN
4551 IF K$(H(R0))<K$(H(S)) THEN 4560
4552 IF L$(H(R0))>=L$(H(S)) THEN RETURN
4560 T=H(R0):H(R0)=H(S):H(S)=T:S=R0:GOTO 4530
4600 IF K$(H(R1))>K$(H(S)) THEN RETURN
4601 IF K$(H(R1))<K$(H(S)) THEN 4660
4602 IF L$(H(R1))>=L$(H(S)) THEN RETURN
4660 T=H(R1):H(R1)=H(S):H(S)=T:S=R1:GOTO 4530
9000 END

Running this code on the Raspberry Pi 4B yields

Code: Select all

$ make
/usr/local/fbc-300/bin/fbc -R -lang qb hanav2.bas
$ time ./hanav2 >hanav2.insane

real    0m10.634s
user    0m9.699s
sys     0m0.931s
$ time ./hanav2 >hanav2.insane

real    0m10.497s
user    0m9.628s
sys     0m0.870s
$ time ./hanav2 >hanav2.insane

real    0m10.543s
user    0m9.682s
sys     0m0.859s
$ md5sum hanav2.insane selfgrams.pl.insane 
addeda36a4631afc983f3bff13742e36  hanav2.insane
addeda36a4631afc983f3bff13742e36  selfgrams.pl.insane

Although the new code is about 2 times faster than before, it still appears near the top of the bar chart.

[Heater]

I wondered about that as well.

I have no idea what they did to the timers in JS but I have always imagined that the inaccuracy introduced was not so big and probably randomized. What we have here is a pretty huge difference consistently.

I get the same results under node.js using it's hrtimer:

Code: Select all

$ ./target/release/insane-british-anagram > temp.txt
515ms
$ node runit.js > temp.txt
287ms

Except the WASM under node.js is even faster !

[Gavinmc42]

Except the WASM under node.js is even faster !

When did node.js become so fast?
What trick is WASM doing?

[bensimmo]

First run and it was some 3400ish I forget ms
But a swipe down to refresh and subsequent runs it's faster at ~2842ms
On my humble Huawei P9 lite handheld computer.

Unfortunately the Nintendo Switch browser doesn't support WASM, probably because it doesn't really support the use of it as a general web browser, so a popular handheld gaming console cannot be benchmarked.

[Heater]

Gavinmc42,

When did node.js become so fast?
What trick is WASM doing?

Node.js was basically the V8 Javascript engine from the Chrome browser wrapped up with libuv and such so as to run on the command line. With a huge bunch of useful functionality added to it's standard libraries/modules. So it was always damn fast as interpreted languages go.

WASM is Web Assembly. It's basically a byte code definition, like Java or C#. You can compile languages like C/C++, Rust and others in to WASM byte code. WASM is now implemented in Chrome and Firefox, no idea about Safari or others. The intention of WASM is to enable faster code execution in the browser with smaller download sizes than Javascript. And it means that many other languages will be usable in the browser, not just Javascript.

It turns out that WASM in Chrome is somehow built into the V8 Javascript engine. So when Chrome got WASM so did node.js. The upshot being that I have now got my Fibonacci Challenge compiled to WASM from C++ and running in the browser. And now the Insane British Anagram solution written in Rust running in the browser. And of course they both run under node.js.

In short, node.js is fast here because it's not running JS. It's running C++ and Rust compiled to WASM byte codes.

As a short and sweet example, this is a simple function in Rust:

Code: Select all

pub extern fn the_answer() -> u32 {
    42
}

This is a disassembly of that function after compiling it to WASM:

www/bare_metal_wasm.wasm: file format wasm 0x1

Code Disassembly:

Code: Select all

000063 <the_answer>:
 000064: 41 2a                      | i32.const 42
 000066: 0b                         | end

Looks like some normal assembler right? Load a constant and return.

But, good grief, how is it possible my code compiled to WASM and interpreted by V8 in the browser or node.js is faster than compiling to native x86 binary?

No, I did not forget to turn optimization on.

I can possibly imagine that the just-in-time compiler in the WASM interpreter is able to do some funky optimizations that a normal compiler cannot because it know how the code behaves at run time.

Or I'm making a big mistake somewhere...

[Heater]

bensimmo,

Thanks for tying that. You get a pretty good speed there.

First run and it was some 3400ish I forget ms
But a swipe down to refresh and subsequent runs it's faster at ~2842ms

Now there is the thing. I tweaked the code to run the anagram finder twice and report the execution time. I build and run it as WASM and native x86 code with the following results:

Code: Select all

$ node runit.js > temp.txt
607ms
290ms
$ ./target/release/insane-british-anagram > temp.txt
507ms
488ms

Clearly the WASM engine has "warmed up" on the second execution. It starts out slower than native code and ends up much faster!

It really is as if it has learned how to optimize that particular code as it runs. That and populating the caches I guess.

I think I have to go back to the Fibo Challenge C++ code and see if the same thing happens with that.