gabriella439 / slides Goto Github PK

Hey Gabriel,

thanks for you talk at ZuriHac.

Regarding https://github.com/Gabriel439/slides/blob/1f18b6b1ca11993a048f51e838322789dcd5dc29/zurihac/slides.md#performance-2, I did a little investigation to help clear that up:

Surprisingly, the pure C example is slower
...
132 MB/s
...
I'm not sure why 🤷

(Yes, I also tried reading blocks instead of individual bytes, unsuccessfully)

fgetc() does read blocks of bytes (as revealed by strace, it reads 4K blocks using read() syscalls).

I think the key thing is that FILE based libc functions, like Haskell's Handle, do fancy character decoding and such, while read() syscalls and ByteString.read don't (also see this).

If I switch to direct read() calls, as the diff below does (it also adds error handling):

--- file.c	2018-06-10 22:54:46.633845400 +0200
+++ file2.c	2018-06-10 23:33:09.981254378 +0200
@@ -1,7 +1,10 @@
 // file.c
 
+#include <errno.h>
 #include <stdlib.h>
 #include <stdio.h>
+#include <unistd.h>
+#include <fcntl.h>
 
 #define NUM_STATES 16
 #define NUM_BYTES 256
@@ -10,7 +13,7 @@
 // Final state: [0..15]
 unsigned char run(
     // Input bytes to process
-    FILE *file,
+    int file_fd,
 
     // Length of the input
     size_t length,
@@ -23,12 +26,30 @@
 ) {
     size_t i, j;
     char currentByte;
-    unsigned char buffer[1000];
+    unsigned char buffer[4096];
     unsigned char currentState = startingState;
 
-    for (i = 0; i < INPUT_SIZE; i++) {
-        currentByte = fgetc(file);
-        currentState = step[currentState][currentByte];
+    while (1) {
+        ssize_t num_read = read(file_fd, buffer, sizeof(buffer));
+
+        if (num_read == -1) {
+            if (errno == EINTR) {
+                continue;
+            } else {
+                perror("read");
+                exit(1);
+            }
+        }
+
+        if (num_read == 0)
+            break;
+
+        for (int c = 0; c < num_read; c++)
+        {
+            currentByte = buffer[c];
+            currentState = step[currentState][currentByte];
+        }
     }
 
     return currentState;
@@ -40,7 +61,7 @@
     unsigned char startingState;
     unsigned char state;
     unsigned char cStyleComments[NUM_STATES][NUM_BYTES] = { 0 };
-    FILE *file;
+    int file_fd;
 
     for (byte = 0; byte < NUM_BYTES; byte++) {
         cStyleComments[0][byte] = 0;
@@ -60,9 +81,17 @@
 
     startingState = 0;
 
-    file = fopen("test.c", "rb");
-    finalState = run(file, INPUT_SIZE, startingState, cStyleComments);
-    fclose(file);
+    file_fd = open("test.c", O_RDONLY);
+    if (file_fd == -1) {
+        perror("open");
+        exit(1);
+    }
+    finalState = run(file_fd, INPUT_SIZE, startingState, cStyleComments);
+    int close_ret = close(file_fd);
+    if (close_ret == -1) {
+        perror("close");
+        exit(1);
+    }
     if (finalState == 0 || finalState == 1) {
         printf("True");
     } else {

Then I get

% gcc -march=native -O3 file2.c -o file2 && /usr/bin/time ./file2
True
1.92user 0.18system 0:02.11elapsed 100%CPU (0avgtext+0avgdata 1400maxresident)k
0inputs+0outputs (0major+64minor)pagefaults 0swaps

instead of

% gcc -march=native -O3 file.c -o file && /usr/bin/time ./file
True
5.45user 0.20system 0:05.66elapsed 99%CPU (0avgtext+0avgdata 1364maxresident)k
0inputs+8outputs (0major+65minor)pagefaults 0swaps
/usr/bin/time ./file  5.45s user 0.21s system 99% cpu 5.664 total

which was the fgetc() based implementation. So a 2.5x speedup.

And for me the Haskell implementation gives:

% /usr/bin/time ./bytes
True
2.20user 0.37system 0:02.58elapsed 99%CPU (0avgtext+0avgdata 979792maxresident)k
0inputs+0outputs (0major+244314minor)pagefaults 0swaps

so the C implementation is slightly faster than the Haskell one.

In your liquidhaskell slides you challenge the readers to break the following:

{-@ abs :: Int -> { n : Int | 0 <= n } @-}
abs :: Int -> Int
abs x = if x < 0 then negate x else x

What about x = minBound :: Int? :-)

Prelude> minBound :: Int
-9223372036854775808
Prelude> negate (minBound :: Int)
-9223372036854775808
Prelude> abs (minBound :: Int)
-9223372036854775808
Prelude> 0 <= (minBound :: Int)
False

I think abs is a bad example, as it is trickier than it seems. (And I'd expect liquidhaskell to catch this.)

I tried using https://mark.show/https://raw.githubusercontent.com/Gabriel439/slides/master/dhall-intro/dhall-intro.md#, but mark.show uses the --- (<hr>; used by reveal.js) to create a slide.

What program did you use to view the slides?

I am getting an error when trying to nix-build --argstr compiler ghc801 release.nix:

these derivations will be built:
/nix/store/xhpzz56f53vh7waq79gfzvkkhgf1vdyw-foldl-1.2.2.drv
/nix/store/36gsl81bycgd0yz4dxgwambw2nrbg1qp-bears-1.0.0.drv
/nix/store/fgiyxhwsxizn3cvhh312dmhmxmkvplsl-bears-doc.drv
/nix/store/m564sylq3xw5asl2w4lbwliz4kci09ph-examples-1.0.0.drv
building path(s) ‘/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0’, ‘/nix/store/i9aa6a9p07kglyrf85lvph4w2fv26zlh-examples-1.0.0-doc’
setupCompilerEnvironmentPhase
Build with /nix/store/m74s3ylqgnpycnhaj1hxqax3xpx9l9z9-ghc-8.0.2.
unpacking sources
unpacking source archive /nix/store/nssnvqgiypnvwss09ngjn1dij10jjyb4-exercises
source root is exercises
patching sources
compileBuildDriverPhase
setupCompileFlags: -package-db=/tmp/nix-build-examples-1.0.0.drv-0/package.conf.d -j1 -threaded
[1 of 1] Compiling Main ( /nix/store/4mdp8nhyfddh7bllbi7xszz7k9955n79-Setup.hs, /tmp/nix-build-examples-1.0.0.drv-0/Main.o )
Linking Setup ...
configuring
configureFlags: --verbose --prefix=/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0 --libdir=$prefix/lib/$compiler --libsubdir=$pkgid --docdir=/nix/store/i9aa6a9p07kglyrf85lvph4w2fv26zlh-examples-1.0.0-doc/share/doc --with-gcc=gcc --package-db=/tmp/nix-build-examples-1.0.0.drv-0/package.conf.d --ghc-option=-optl=-Wl,-rpath=/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/lib/ghc-8.0.2/examples-1.0.0 --ghc-option=-j1 --disable-split-objs --disable-library-profiling --disable-profiling --enable-shared --disable-coverage --enable-library-vanilla --enable-executable-dynamic --enable-tests --ghc-option=-split-sections
Configuring examples-1.0.0...
Dependency base <5: using base-4.9.1.0
Dependency bytestring -any: using bytestring-0.10.8.1
Dependency cassava -any: using cassava-0.4.5.1
Dependency containers -any: using containers-0.5.7.1
Dependency diagrams-lib -any: using diagrams-lib-1.4.1.2
Dependency diagrams-svg -any: using diagrams-svg-1.4.1.1
Dependency discrimination -any: using discrimination-0.2.1
Dependency lens -any: using lens-4.15.4
Dependency text -any: using text-1.2.2.2
Dependency vector -any: using vector-0.12.0.1
Using Cabal-1.24.2.0 compiled by ghc-8.0
Using compiler: ghc-8.0.2
Using install prefix:
/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0
Binaries installed in:
/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin
Libraries installed in:
/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/lib/ghc-8.0.2/examples-1.0.0
Dynamic libraries installed in:
/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/lib/ghc-8.0.2/x86_64-linux-ghc-8.0.2
Private binaries installed in:
/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/libexec
Data files installed in:
/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/share/x86_64-linux-ghc-8.0.2/examples-1.0.0
Documentation installed in:
/nix/store/i9aa6a9p07kglyrf85lvph4w2fv26zlh-examples-1.0.0-doc/share/doc
Configuration files installed in:
/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/etc
No alex found
Using ar found on system at:
/nix/store/z470j6lybdsy4ql972k392490bprhd2g-binutils-2.28.1/bin/ar
No c2hs found
No cpphs found
Using gcc version 6.4.0 given by user at:
/nix/store/kd7vb1afwvm2k65n9qjdw767w6lnwsrd-gcc-wrapper-6.4.0/bin/gcc
Using ghc version 8.0.2 found on system at:
/nix/store/m74s3ylqgnpycnhaj1hxqax3xpx9l9z9-ghc-8.0.2/bin/ghc
Using ghc-pkg version 8.0.2 found on system at:
/nix/store/m74s3ylqgnpycnhaj1hxqax3xpx9l9z9-ghc-8.0.2/bin/ghc-pkg
No ghcjs found
No ghcjs-pkg found
No greencard found
Using haddock version 2.17.3 found on system at:
/nix/store/m74s3ylqgnpycnhaj1hxqax3xpx9l9z9-ghc-8.0.2/bin/haddock
No happy found
Using haskell-suite found on system at: haskell-suite-dummy-location
Using haskell-suite-pkg found on system at: haskell-suite-pkg-dummy-location
No hmake found
Using hpc version 0.67 found on system at:
/nix/store/m74s3ylqgnpycnhaj1hxqax3xpx9l9z9-ghc-8.0.2/bin/hpc
Using hsc2hs version 0.68.1 found on system at:
/nix/store/m74s3ylqgnpycnhaj1hxqax3xpx9l9z9-ghc-8.0.2/bin/hsc2hs
No hscolour found
No jhc found
Using ld found on system at:
/nix/store/kd7vb1afwvm2k65n9qjdw767w6lnwsrd-gcc-wrapper-6.4.0/bin/ld
No lhc found
No lhc-pkg found
No pkg-config found
Using strip version 2.28 found on system at:
/nix/store/z470j6lybdsy4ql972k392490bprhd2g-binutils-2.28.1/bin/strip
Using tar found on system at:
/nix/store/kpnj0h0340wd0i86q0523527ikbz62ll-gnutar-1.29/bin/tar
No uhc found
building
Building examples-1.0.0...
Preprocessing executable 'example-00' for examples-1.0.0...
[1 of 1] Compiling Main ( 00/Main.hs, dist/build/example-00/example-00-tmp/Main.dyn_o )
Linking dist/build/example-00/example-00 ...
Preprocessing executable 'example-01' for examples-1.0.0...
[1 of 1] Compiling Main ( 01/Main.hs, dist/build/example-01/example-01-tmp/Main.dyn_o )
Linking dist/build/example-01/example-01 ...
Preprocessing executable 'example-02' for examples-1.0.0...
[1 of 1] Compiling Main ( 02/Main.hs, dist/build/example-02/example-02-tmp/Main.dyn_o )
Linking dist/build/example-02/example-02 ...
Preprocessing executable 'example-03' for examples-1.0.0...
[1 of 1] Compiling Main ( 03/Main.hs, dist/build/example-03/example-03-tmp/Main.dyn_o )
Linking dist/build/example-03/example-03 ...
Preprocessing executable 'example-04' for examples-1.0.0...
[1 of 1] Compiling Main ( 04/Main.hs, dist/build/example-04/example-04-tmp/Main.dyn_o )
Linking dist/build/example-04/example-04 ...
Preprocessing executable 'example-05' for examples-1.0.0...
[1 of 1] Compiling Main ( 05/Main.hs, dist/build/example-05/example-05-tmp/Main.dyn_o )
Linking dist/build/example-05/example-05 ...
Preprocessing executable 'example-06' for examples-1.0.0...
[1 of 1] Compiling Main ( 06/Main.hs, dist/build/example-06/example-06-tmp/Main.dyn_o )
Linking dist/build/example-06/example-06 ...
Preprocessing executable 'example-07' for examples-1.0.0...
[1 of 1] Compiling Main ( 07/Main.hs, dist/build/example-07/example-07-tmp/Main.dyn_o )
Linking dist/build/example-07/example-07 ...
Preprocessing executable 'example-08' for examples-1.0.0...
[1 of 1] Compiling Main ( 08/Main.hs, dist/build/example-08/example-08-tmp/Main.dyn_o )
Linking dist/build/example-08/example-08 ...
running tests
Package has no test suites.
haddockPhase
installing
Installing executable(s) in
/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin
Warning: The directory
/nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin is not in the
system search path.
post-installation fixup
shrinking RPATHs of ELF executables and libraries in /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0
shrinking /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin/example-02
shrinking /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin/example-06
shrinking /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin/example-04
shrinking /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin/example-00
shrinking /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin/example-03
shrinking /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin/example-01
shrinking /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin/example-07
shrinking /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin/example-08
shrinking /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin/example-05
stripping (with flags -S) in /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0/bin
patching script interpreter paths in /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0
checking for references to /tmp/nix-build-examples-1.0.0.drv-0 in /nix/store/c0avc2ax1vdswq4n4hawjmlq3zvk4xh9-examples-1.0.0...
shrinking RPATHs of ELF executables and libraries in /nix/store/i9aa6a9p07kglyrf85lvph4w2fv26zlh-examples-1.0.0-doc
patching script interpreter paths in /nix/store/i9aa6a9p07kglyrf85lvph4w2fv26zlh-examples-1.0.0-doc
checking for references to /tmp/nix-build-examples-1.0.0.drv-0 in /nix/store/i9aa6a9p07kglyrf85lvph4w2fv26zlh-examples-1.0.0-doc...
building path(s) ‘/nix/store/0hj9x5rngx20vg2jm9cglqarg15a60ip-foldl-1.2.2’, ‘/nix/store/p4sfy37xgdipyp6mb8rcajlgc07qfwyb-foldl-1.2.2-doc’
setupCompilerEnvironmentPhase
Build with /nix/store/m74s3ylqgnpycnhaj1hxqax3xpx9l9z9-ghc-8.0.2.
unpacking sources
unpacking source archive /nix/store/vlvp9lpm2963id69v5ixmx15xagabang-foldl-1.2.2.tar.gz
source root is foldl-1.2.2
setting SOURCE_DATE_EPOCH to timestamp 1483230235 of file foldl-1.2.2/CHANGELOG.md
patching sources
compileBuildDriverPhase
setupCompileFlags: -package-db=/tmp/nix-build-foldl-1.2.2.drv-0/package.conf.d -j1 -threaded
[1 of 1] Compiling Main ( Setup.hs, /tmp/nix-build-foldl-1.2.2.drv-0/Main.o )
Linking Setup ...
configuring
configureFlags: --verbose --prefix=/nix/store/0hj9x5rngx20vg2jm9cglqarg15a60ip-foldl-1.2.2 --libdir=$prefix/lib/$compiler --libsubdir=$pkgid --docdir=/nix/store/p4sfy37xgdipyp6mb8rcajlgc07qfwyb-foldl-1.2.2-doc/share/doc --with-gcc=gcc --package-db=/tmp/nix-build-foldl-1.2.2.drv-0/package.conf.d --ghc-option=-optl=-Wl,-rpath=/nix/store/0hj9x5rngx20vg2jm9cglqarg15a60ip-foldl-1.2.2/lib/ghc-8.0.2/foldl-1.2.2 --ghc-option=-j1 --disable-split-objs --disable-library-profiling --disable-profiling --enable-shared --disable-coverage --enable-library-vanilla --enable-executable-dynamic --enable-tests --ghc-option=-split-sections
Configuring foldl-1.2.2...
Setup: Encountered missing dependencies:
vector >=0.7 && <0.12
builder for ‘/nix/store/xhpzz56f53vh7waq79gfzvkkhgf1vdyw-foldl-1.2.2.drv’ failed with exit code 1
cannot build derivation ‘/nix/store/36gsl81bycgd0yz4dxgwambw2nrbg1qp-bears-1.0.0.drv’: 1 dependencies couldn't be built
cannot build derivation ‘/nix/store/fgiyxhwsxizn3cvhh312dmhmxmkvplsl-bears-doc.drv’: 1 dependencies couldn't be built
error: build of ‘/nix/store/fgiyxhwsxizn3cvhh312dmhmxmkvplsl-bears-doc.drv’ failed

Thank you @Gabriel439 for the talk. I'm interested in how Dhall is being used for governance. Are you able to disclose what organization is using Dhall for their governance? Is there a sample org doc or contract? This could be a "killer app".

https://youtu.be/ikEx56F6g1M?t=6249

Like at the end, a note "all code in these slides is hereby MIT licensed, text below" or something... I can do a PR if you like. We're thinking of adapting it for regex support in Unison, where we want something simple and performant.

Also thanks for writing and sharing the slides! It was fun reading.