Writings about software development.

Solving Scheduling With Z3 from Rust

This post is a translation of a Z3 example from Python to Rust. It is not very inspired: Please read the original Python article 1 for more background. However, at the bottom of this page, I provide a few more links and resources with a few notes. The Z3 crate does not have any examples, so it makes it a bit tough to …

Read full article Collapse article : Solving Scheduling With Z3 from Rust

A translation of a Z3 example from Python to Rust

This post is a translation of a Z3 example from Python to Rust. It is not very inspired: Please read the original Python article 1 for more background. However, at the bottom of this page, I provide a few more links and resources with a few notes.

The Z3 crate does not have any examples, so it makes it a bit tough to get started. I found one article that explains how to use Z3 for scheduling tasks in Python.

Result

Here’s the result of running the scheduler. The goal is to minimize the total time taken for the tasks. Each row has to be done in order (t1, t2, t3, then t4). And tasks of the same color cannot be scheduled at the same time.

Table of Python to Rust
Python Rust
Initialization opt = Optimize() let cfg = Config::new(); let ctx = Context::new(&cfg); let opt = Optimize::new(&ctx);
opt.add(tx[i] + task_length[i] <= tx[j]) opt.assert(&(&tasks[&i] + &task_length[&i]).le(&tasks[&j]));
Operators a < b 🙂 a.lt(&b) 😕 2
If If(a, b, c) a.ite(b, c)

The Translation

I’ve kept the code as close to possible as to the original Python. Personally, I would make few simplifications, like using itertools::choose function to get all combinations of the color groupings.

use std::collections::BTreeMap;

use z3::ast::Bool;
use z3::*;

fn main() {
    // Python: opt = Optimize()
    let cfg = Config::new();
    let ctx = Context::new(&cfg);
    let opt = Optimize::new(&ctx);

    let task_length: BTreeMap<i32, u64> = BTreeMap::from([
        (1, 20),
        (2, 50),
        (3, 80),
        (4, 50),
        (5, 60),
        (6, 45),
        (7, 20),
        (8, 25),
        (9, 50),
        (10, 30),
        (11, 40),
        (12, 50),
    ]);

    // tasks = {k: Int("t{}".format(k)) for k in task_length.keys()}
    let tasks: BTreeMap<_, _> = task_length
        .keys()
        .map(|k| (k, ast::Int::new_const(&ctx, format!("t{}", k))))
        .collect();

    // opt.add(And([t >= 0 for t in tasks.values()]))
    let zero = ast::Int::from_u64(&ctx, 0);
    for t in tasks.values() {
        opt.assert(&t.ge(&zero));
    }

    // tend = Int("tend")
    let tend = ast::Int::new_const(&ctx, "tend");

    let edges = [
        (1, 2),
        (2, 3),
        (3, 4),
        (5, 6),
        (6, 7),
        (7, 8),
        (9, 10),
        (10, 11),
        (11, 12),
    ];

    for (i, j) in edges {
        opt.assert(&(&tasks[&i] + task_length[&i]).le(&tasks[&j]));
    }
    let ends = [4, 8, 12];
    for i in ends {
        opt.assert(&(&tasks[&i] + task_length[&i]).le(&tend));
    }

    // Coloring restrictions
    let add_related_constraint = |a, b| {
        let bo = Bool::new_const(&ctx, format!("b{},{}", a, b));
        opt.assert(&bo.ite(
            &(&tasks[&a] + task_length[&a]).le(&tasks[&b]),
            &(&tasks[&b] + task_length[&b]).le(&tasks[&a]),
        ));
    };

    add_related_constraint(1, 5);
    add_related_constraint(5, 11);
    add_related_constraint(1, 11);

    add_related_constraint(2, 7);
    add_related_constraint(7, 9);
    add_related_constraint(2, 9);

    add_related_constraint(3, 8);
    add_related_constraint(8, 10);
    add_related_constraint(3, 10);

    add_related_constraint(4, 6);
    add_related_constraint(6, 12);
    add_related_constraint(4, 12);

    // opt.minimize(tend)
    opt.minimize(&tend);
    assert_eq!(opt.check(&[]), SatResult::Sat);
    // m = opt.model()
    let m = opt.get_model().unwrap();

    for i in task_length.keys() {
        println!("{} {}", tasks[i], &m.eval(&tasks[i], true).unwrap());
    }

    println!("{} {}", tend, m.eval(&tend, true).unwrap());
}

Notes

  • My z3 version: z3 = {version="0.11.2", features = ["static-link-z3"]}

Further Reading

https://docs.rs/z3/latest/z3

  • The documentation of the high level z3 crate.
  • It is helpful but not sufficient for beginners. (I’m a beginner.)

https://web.imt-atlantique.fr/x-info/cpaior-2012/uploads/slides%20master%20class/5-scheduling-Hebrard.pdf

  • Scheduling and SAT by Emmanuel Hebrard of LAAS-CNRS, Toulouse
  • Explanations!
  • Graphs and in-detail example exactly the same as in the code in my post.

https://sat-smt.codes/SAT_SMT_by_example.pdf

  • A good explanation

https://github.com/alex-chew/z3d-rs

  • Has examples
  • Last commit 3 years ago
  • Uses z3 crate but adds macros on top.
  • You can write: opt.assert(&exp!((num >= 0) & (num <= 9) in ctx));. i.e. you can use x > y etc instead of x.gt(&y).
  • Does not work on Rust stable due to the usage features box_patterns and proc_macro_hygiene.
  • Extremely slow to compile.

https://github.com/prove-rs/z3.rs/tree/master/z3/tests

  • Tests serve as examples

https://fitzgeraldnick.com/2020/01/13/synthesizing-loop-free-programs.html

https://cprimozic.net/blog/a-rusty-aoc/#day-23-using-the-z3-smt-solver

https://ericpony.github.io/z3py-tutorial/guide-examples.htm

  • Examples in Python
  • See my table of Python to Rust for help in translating.

https://github.com/prove-rs/z3.rs/issues/151

  • A GitHub ticket with a request for more examples
  • Links to further resources
Open article page →

Apple M1 Performance Cycles

A short update: I just published my second crate (a Rust package): https://crates.io/crates/macos-perf I hope this can be used to accurately measure Rust code on M1 Apple devices. Please try it, and provide feedback. Running the example code I provide gives the following results: sudo cargo run --quiet --example main …

Read full article Collapse article : Apple M1 Performance Cycles

A short update: I just published my second crate (a Rust package): https://crates.io/crates/macos-perf

I hope this can be used to accurately measure Rust code on M1 Apple devices.

Please try it, and provide feedback.

Example

Running the example code I provide gives the following results:

sudo cargo run --quiet --example main
PerformanceCounters {
    cycles: 46148.1,
    branches: 23053.4,
    missed_branches: 2.4,
    instructions: 162342.9,
}

We see the missed branches, cycles, branches taken and instructions. Unfortunately, none of this is documented by the vendor (Apple). But, Dougall Johnson wrote code to interact with the undocumented macOS syscalls. So, this is what my library uses.

The above output was generated by the below code, in case you’re interested:

/// You need to run this with sudo.
use criterion::black_box;
use macos_perf::{init, timeit_loops};

fn main() {
    init().unwrap();
    let pc = timeit_loops! {10, {
        let n = black_box(1000);
        let _x = (0..n).fold(0, |a, b| a ^ b);
    }}
    .unwrap();
    println!("{:#?}", pc);
}

Initial Measurements

Performance Counters and measured time are clearly correlated

This plot shows that performance counters and measured runtime are correlated.

I used the Matrix multiplication benchmarking code that I already had, and also run the macos-perf counter code on it.

The resulting plot shows that performance counters and measured runtime are correlated.

But out of one program (with its unique characterisk effects on branches, cache misses, etc), is not enough to build a good model to predict runtime from measured counters. So, I clearly have more work ahead of me.

Conclusion

There’s no conclusion. This is only an intermediate step which I wanted to share.

Open article page →

Rust Serde Versioning

Serde is an amazing collection of Rust libraries for Serialization and Deserialization with many useful supported formats. For example, I can convert a YAML file into a native Rust struct by just slapping a #[derive(Deserialize)] above the struct. One challenge that I faced was reading YAML files of different schema …

Read full article Collapse article : Rust Serde Versioning

Serde is an amazing collection of Rust libraries for Serialization and Deserialization with many useful supported formats.

For example, I can convert a YAML file into a native Rust struct by just slapping a #[derive(Deserialize)] above the struct.

One challenge that I faced was reading YAML files of different schema versions.

One option is to use Option<T> for all fields which changed between versions. Generally speaking, this is probably the easiest and most suitable solution. However, when parsing is also used as a linter, this will not suffice. For example, we might have a version 1.0 that has fields a and b (both required). In version 2.0, only a remains and b is replaced by c.

To solve this, I found that tagged enums make for the best representation.

Here’s an example input file:

my_version: 1.0
a: "bla"
b: "blub"

Here’s the MyFile enum, internally tagged on the field my_version:

#[derive(Debug, Deserialize)]
#[serde(tag = "my_version")]
enum MyFile {
    #[serde(rename = "1.0")]
    V1(MyFileV1),
    #[serde(rename = "2.0")]
    V2(MyFileV2),
}

And the MyFileV1 looks like this:

#[derive(Debug, Deserialize)]
#[serde(deny_unknown_fields)]
struct MyFileV1 {
    a: String,
    b: String,
}

You can see a free standing example here on the Rust playground.

Open article page →

Rust CLI Video Tutorial

A while back, I posted my first Rust Video. In it, I am showing how to write a simple command line application in Rust – including useful libraries. The CLI is mimicking the GNU shuf utility: It randomly shuffles files of an input file.

Read full article Collapse article : Rust CLI Video Tutorial

A while back, I posted my first Rust Video. In it, I am showing how to write a simple command line application in Rust – including useful libraries.

The CLI is mimicking the GNU shuf utility: It randomly shuffles files of an input file.

Libraries used:

Along the way we also see the usefulness of the Rust Analyzer.

I hope you enjoy it. If you do, please let me know your thoughts by dropping any comments to my Twitter.

Open article page →

Practical Tips for Advanced Git Bisect

This is an adaptation from my Twitter thread: Git Bisect Thread I assume you’ve used or heard of git bisect. If you’ve neither heard off nor used git bisect before, then I encourage you to give it a try. Franziska Hinkelmann provides a good intro and a test repo to find a bug with git bisect. Recap: git bisect start …

Read full article Collapse article : Practical Tips for Advanced Git Bisect

Practical Notes on Advanced Git Bisect

This is an adaptation from my Twitter thread:

Recap of Bisect

I assume you’ve used or heard of git bisect. If you’ve neither heard off nor used git bisect before, then I encourage you to give it a try. Franziska Hinkelmann provides a good intro and a test repo to find a bug with git bisect.

Recap:

  1. git bisect start BAD GOOD
  2. <RUN TEST>
  3. label result with git bisect good or ... bad (or skip)
  4. Goto 2 until git bisect tells you it’s done.

This then does a binary search1 through all commits between the GOOD and the BAD commit. After each step you have to label the current commit with good, bad or skip. Because binary search halfs the search range in every step, the number of commits to check is approximately log2(N), where N is the number of commits between GOOD and BAD. This means you can check 1000 commits in just 10 steps!


Do yourself the favor and always start git bisect with the good and bad commits! That way you can “git bisect reset” it later, and start over using your shell history.

git bisect start BAD GOOD

git bisect start main v0.1.0 # Assuming that main is bad and v0.1.0 is good.

This is not necessary.

You can also just start with git bisect start and then git checkout BAD; git bisect bad and the same for the bad commit. But as I always mess up, it is just easier to keep this in the shell command directly.

Of course, you can also inspect what the initial good/bad commits were with git bisect log.

How to remember what comes first in the arguments? Well, git is a naughty program, so BAD comes first. 😉


Ignore Feature Branches

You probably want --first-parent. This has been only available in Git since v2.29 (Q4 2020) 4.

In good Git tradition, it is confusingly named. Essentially it only considers changes directly on main. Feature branches are ignored.

This option is particularly useful in avoiding false positives when a merged branch contained broken or non-buildable commits, but the merge itself was OK. 1

Use it like so: git bisect start --first-parent main v0.1.0

Filter Directories

You can filter directories or files by starting it like this: git bisect start -- <path> . Only commits which modify <path> will be considered.

This is less useful in practice because of the logarithmic nature of binary search. Having only half the commits to search through saves only a single step. -- first-parent will help more.


Fix Your Mistakes

I always mess up, so I save the result:

  1. git bisect log > ../bisect.log
  2. Fix your mistakes in ../bisect.log
  3. Start again: git bisect replay ../bisect.log

(Put the log outside your git dir, otherwise your repo is dirty.)


Run

This is where the advanced usage of git bisect starts.

git bisect run is awesome and plays well with Unix tools.

For example, if you remember make, you can use it like this to find build failures: git bisect run make

git bisect run make -C <build_dir> if you use CMake and have configured it once before. (do yourself a favor and put it completely outside your repo)


This works for almost anything:

  • git bisect run cargo test
  • git bisect run npm test
  • git bisect run yarn test
  • git bisect run cargo run

However, when it is that easy to run bisect, you should’ve added this to CI long ago.

If the one line does not work, write a script –>

Bisect Scripts

Run scripts like so: git bisect run ~/custom_script.sh

  1. Put them outside the repo.
  2. Test them manually first.
  3. “set -e” is good.
  4. Know about exit codes. 0: good, 1-124: bad. 125: skip. 126-255: abort.
  5. Only one line should return “bad” (1-124).
  6. Exit 125 is for skipping commits!

Use the aborting exit codes to know where the script failed.

cmake -B /tmp/build -S . || exit 128
make -C /tmp/build || exit 129

The exit code will tell you which step failed.

If you want to skip build failures, use exit code 125.

cmake -B /tmp/build -S . || exit 125
make -C /tmp/build || exit 125
make tests

Scripts: “Are we there, yet?”

Some scripts take very long. The below command tells you how many commits remain. You can run it in a second terminal.

git bisect visualize --oneline | wc -l.

The number of remaining scripts is approximately ceil(log2 ( N )) where N is the result from the line before. 2


After your script has run, immediately save the run in a log!

git bisect log > ../bisect_run.log

Again git bisect replay let’s you fix any mistakes.


Check your bisect results! (This literally happened to me while writing this thread.)

Repeat your script and see if the output of the first breaking commit is the same error that you were looking for.

If not, make your check more specific. For example, by piping stderr through grep -q.

Philosophy

Things where git bisect will not work.

  • Undefined Behavior.
  • Non-deterministic builds. Clean your build. Lock your manifest file!
  • In summary, if the result depends on the previous checked out commit in anyway the whole process falls apart.

Prefer correctness over speed, especially if you wrote a run script.

There will be ~10 steps. If it is automatic and runs in the background it can take twice the time. Having to do it three times because the script found the wrong answer because you messed up takes longer.

Maybe I can convince you that if you have a script that you can trust, you can have a coffee, or work on something else. If you cannot trust your script, then you will have to manually check multiple times.

An easy way to do so is to throw your build artifacts away!

BUILD_DIR=$(mktemp -D)
cmake -B $BUILD_DIR ...

Hilarious things that went wrong WHILE WRITING THIS THREAD.

  1. Did not use cargo clean and regretted it.
  2. Did not grep for the exact error and found a different error.

All your labels are bad or good? Your script is probably broken.

Remember, if the bug introduction is uniformly distributed, binary search should have bad/good 50% each. Even if there’s a heavy skew because you started with a really early version, 100% one way is unlikely.


When Git Bisect Is Helpful

git bisect is mostly good for features that you didn’t have under test.

Bad reason: Unit tests fail. (Just add ’em to CI.) Good reason: A user reports a regression on a platform you cannot easily have in CI.

Bad reason: (In C++), a new problem cannot be reproduced in a Debug build, or with printf statements added. (You very likely have UB, and the bug won’t be deterministic between builds.)

Another good reason: Working on an unfamiliar code base.

Probabilistic Bisect

And finally, if you ever find a good use case for probabilistic (Bayesian Search) bisect, please, please let me know.

I haven’t had bugs that looked random actually be random. Mostly they’re just depending on something outside “the system”.

https://github.com/siedentop/bbchop https://en.wikipedia.org/wiki/Bayesian_search_theory

Even More Details

Want to learn how the algorithm works? And why it is not simply binary search?

Christian Couder wrote about it: https://mirrors.edge.kernel.org/pub/software/scm/git/docs/git-bisect-lk2009.html


Resources:

1, 2, 3.

https://stackoverflow.com/questions/17267816/git-bisect-with-merged-commits https://twitter.com/chsiedentop/status/1305636746122592256 https://mirrors.edge.kernel.org/pub/software/scm/git/docs/git-bisect-lk2009.html


  1. Below I will explain why this is not exactly binary search in the presence of branches. ↩︎

  2. You could compute that using awk or bc. However, it takes me too long to figure this out, and computing approximate log2 is easy enough. For the record it is echo 65 | awk '{a = log($1)/log(2); printf("%0.1f\n", a)}'. ↩︎

Open article page →

Optimizing C++ Word Count

Yesterday’s post showed that the original C++ version is around 13 times slower than my non-optimized Rust version. Next, I’ll show how to get easily equivalent performance to Rust. One problem that I immediately made out when first seeing the C++ version is that it uses std::regex. std::regex is known to be horribly …

Read full article Collapse article : Optimizing C++ Word Count

Yesterday’s post showed that the original C++ version is around 13 times slower than my non-optimized Rust version. Next, I’ll show how to get easily equivalent performance to Rust.

One problem that I immediately made out when first seeing the C++ version is that it uses std::regex. std::regex is known to be horribly slow 1.

Just replacing the checking of the file name extension with the in-built e.path().extension() != ".txt" speeds up from 373 ms to 52ms!

Before:

const std::regex fname_regex("\\.txt$", std::regex_constants::icase);
// ...
if (!std::regex_search(e.path().c_str(), fname_regex)) {
    continue;
}

After:

if (e.path().extension() != ".txt") {
    continue;
}

Next, I set out to replace the splitting into words with std::regex. I decided to use CTRE because I have never had a chance to use it before. CTRE stands for Compile-Time Regular Expressions, and means that the matching pattern is compiled into a regex matcher.

Unfortunately, I could not get Conan to work with it2. So, I copied the single header file (apologies!).

The result looks like this:

static constexpr auto word_regex = ctll::fixed_string{"([a-zA-Z]{2,})"};
// ...
for (auto match : ctre::range<word_regex>(line)) {
   auto word = match.get<0>();
   ++word_counts[std::string(word)];
}

Numbers

The final performance numbers including Go 3 show C++, Rust and Go fairly close to each other. Please run your own benchmarks (use hyperfine) on your relevant workload. I suspect that Go’s runtime takes a few milliseconds to start.

Needless to say, I made sure that all comparisons were done on the same directory and with release builds.

On the C++ side we went from 373 ms to 52ms to 23ms, a 15x improvement.4

Command Mean [ms] Min [ms] Max [ms] Relative
cpp/word-count 23.0 ± 1.9 20.3 32.7 1.00
rust/words 26.9 ± 1.6 23.6 31.2 1.17 ± 0.12
go/wordcount 43.5 ± 3.3 39.2 55.6 1.89 ± 0.21
swift/word-count 84.3 ± 5.0 79.4 103.5 3.67 ± 0.37

Update

After publishing this, I saw this post by Jussi Pakkanen, where they make the same changes to the extension checking.

And I realize that the point of their exercise was to only use the C++ Standard Library. That necessarily precludes the usage of CTRE.


  1. I recommend watching Hana Dusíková’s talks on her CTRE library. Brilliant! ↩︎

  2. This is the third try I gave Conan and there’s always something not quite working. In this case, Conan was expecting clang 9 but I had clang 12. Clang 12 isn’t known to Conan. Then, CTRE was was expecting C++17 and even setting cppstd=17 did not help. ↩︎

  3. And when running the Go version for the first time, I get a runtime error. Irony. panic: runtime error: slice bounds out of range [:10] with capacity 0. Running it in a directory with txt-files prevents the error. ↩︎

  4. For the curious, I generated the table with the following command: hyperfine --warmup=2 /full/path/to/rust /full/path/to/swift ... --export-markdown version1.md. Providing warmup=2 could be controversial. All of it was on macOS 10.15. ↩︎

Open article page →

Swift Word Count

Yesterday, I wrote about implementing word-count in Rust. Having never written Swift before1, I wanted to try my hand at the same problem. This is certainly not comparable to my Rust version or the C++ version 2. Doing this in Swift just consisted of constant googling and the result is certainly not what a proficient …

Read full article Collapse article : Swift Word Count

Yesterday, I wrote about implementing word-count in Rust. Having never written Swift before1, I wanted to try my hand at the same problem.

This is certainly not comparable to my Rust version or the C++ version 2. Doing this in Swift just consisted of constant googling and the result is certainly not what a proficient Swifter would write.

Getting started

I created a new Swift package, and built it in the command line. All three commands need no explanation:

  1. swift package init --type executable
  2. swift build
  3. swift run

However, when opening it later in XCode, it was necessary to add a products field in the Package.swift declaration. Otherwise, XCode does not run it in a shell or shows output.

The Result

Here is what I came up with after a long while. Finding FileHandle and FileManager as the primary APIs to use, was natural.

import Foundation

var counter: [String: Int] = [:]

let folderPath = "."
let enumerator = FileManager.default.enumerator(atPath: folderPath)
let filePaths = enumerator?.allObjects as! [String]
// NOTE: I would guess that there is a way to handle this without converting paths to a string, and hence also joining the folder with the file easier.
// BUG: my implementation keeps newline control characters.

let txtFilePaths = filePaths.filter { $0.contains(".txt") }
for txtFilePath in txtFilePaths {
  let fh = FileHandle.init(forReadingAtPath: folderPath + "/" + txtFilePath)
  let data = fh?.readDataToEndOfFile()
  let content = String(data: data ?? Data(), encoding: .utf8)

  _ = content?.split(separator: " ").map(
    {
      word -> Void in
      counter[String(word), default: 0] += 1
    }
  )
}

var words = counter.map({ (key, count) in (count, key) })
words.sort(by: { $0.0 > $1.0 })
for (c, w) in words.prefix(10) {
  print("\(w) \(c)")
}

Notes

I am not happy with the fact that FileManager’s DirectoryEnumerator cannot be used as a Path-API (again, please tell me if I’m wrong). It seems that the only way to use it, is by converting it first to strings.

This leads to ugly code like folderPath + "/" + txtFilePath.

Next - coming from Rust - the question-mark operator was confusing. But after reading the official documentation (instead of just fighting the compiler), it snapped into place. Initially, I used a lot of if let x = ..., but in the end, the only place I could not replace them with a ?, was with creating a String from data.

I settled on the double question marks, which provide a default. data ?? Data(), either de-optionalizes the data or creates an empty Data.

I like the clarity of this: counter[String(word), default: 0] += 1. It is not overly verbose. I’ve written the same line in Rust as *counter.entry(w).or_insert(0) += 1;. I think Swift is more readable.

Some common functionality which is available in Rust (and C++) seems to be missing in Swift. For example, content?.split(separator: " "). This only splits spaces, not generally whitespace. Again, since this was my first day writing Swift, I could have easily missed the right function.

Performance

I checked performance using hyperfine. All programs were compiled with the default Release configuration3.

Please do not read anything into these numbers. I do not know how to write Swift, and I was able to fix the C++ code (next post).

Command Mean [ms] Min [ms] Max [ms] Relative
swift/word-count 85.3 ± 4.7 81.3 106.0 3.01 ± 0.49
rust/words 28.3 ± 4.3 24.3 50.8 1.00
cpp/word-count 372.9 ± 30.2 346.4 436.2 13.17* ± 2.26

After I eliminated the infamously slow std::regex from the C++ version, this is what the table looked like.

Command Mean [ms] Min [ms] Max [ms] Relative
swift/word-count 85.2 ± 5.5 81.4 110.8 3.52 ± 0.56
rust/words 27.2 ± 2.4 24.7 40.4 1.12 ± 0.19
cpp/word-count 24.2 ± 3.5 20.0 34.3 1.00

Summary

It’s fine. Use whatever you already know or what your friends use.

Next up, read on how to make C++ faster than Rust and Go.


Grievances

  • Getting swift-format to work
  • Frequent build failure ()
  • VSCode isn’t great. Apple’s LSP implementation “SourceKit-LSP” does not have a VSCode-extension. So you have to build it yourself and manually install it. I did and failed.
  • I heard of Swiftenv. Didn’t end up using it as it seemed unnecessarily complicated for my use case. But maybe it would have made my life easier.
  • FileHandle::readDataToEndOfFile seems to be deprecated. At least I got warnings about this, until I stopped using VSCode. The docs to FileHandle mention various deprecations. While I think deprecating APIs is fine, this happening literally on my first API from the standard library left me with an uneasy feeling about instable APIs. Was I just unlucky, or are all base libraries in constant flux?

  1. Except the Swift-Playground on the iPad. ↩︎

  2. I’ve updated the original C++ code but that is for another post. ↩︎

  3. I’ve modified the command path to conserve horizontal space. ↩︎

Open article page →

Rust Word Count

Last week there were two posts on the reputation of C++. In a noble effort, Jussi Pakkanen showcased modern C++. Nothing fancy, just clean and readable code. Unfortunately, around ten years after C++11, the news that simple (and safe) C++ code is now the default has not spread everywhere. Jason Moiron answered with Go …

Read full article Collapse article : Rust Word Count

Last week there were two posts on the reputation of C++. In a noble effort, Jussi Pakkanen showcased modern C++. Nothing fancy, just clean and readable code. Unfortunately, around ten years after C++11, the news that simple (and safe) C++ code is now the default has not spread everywhere.

Jason Moiron answered with Go code doing the same (article). Both programs find the ten most common words in all txt files, which can be recursively found in the current directory.

Both articles are much better than this one, so I urge you to read them first.

  1. Does C++ still deserve the bad rap it has had for so long?
  2. C++ Deserves Its Bad Reputation

I wanted to see what this would look like in Rust.

The final result can be found in this Gist.

Analysis

Stand-Alone

The C++ article mentioned that C++ is the only language where all necessary features are in the standard library. And looking at my Cargo.toml file, you’ll see that I use these two external dependencies.

[dependencies]
walkdir = "2.3.1"
anyhow = "1.0.33"

I would argue that having a healthy package collection is extremely important. Rust certainly has this and using external dependencies is a joy.

However, I do see a certain irony in the fact that on anything larger, I would replace anyhow with color-eyre for more functionality (like .suggestion(...) on errors). And ignore::WalkBuilder can replace walkdir while providing inbuilt parallelism.

Question-Mark Operator

fn main() -> Result<()> { ... }

In Rust, the main function can optionally return a Result, which means that the excellent bubble-up-errors operator (?)1 can be used. It is Rust’s shorthand for returning early in case of an Error.

Type Interference

let mut counter = std::collections::BTreeMap::new();

This should be simple enough. Rust uses let to declare variables with type interference. To give the best of both worlds, it is also possible to provide type annotations, although this is normally only done where automatic type annotation fails2.

Note that everything is constant unless mut is provided. I must admit that I find that sometimes annoying; even though I wholeheartedly agree with it on principle.

Functional

The next part, is in my opinion, the biggest criticism of the readability and cleanliness of this code example.

for entry in WalkDir::new(".")
    .follow_links(true)
    .into_iter()
    .filter_map(|e| e.ok())
    .filter(|e| e.file_name().to_string_lossy().ends_with(".txt"))
{
    ...
}

My first criticism is that here we mix business-logic with boiler-plate. I am talking about .into_iter(). While you’ll become accustomed to this, since it is very common in Rust code, it is nothing we care about from a functionality side.

Next, all this Functional Programming style will take some getting used to for those of us with Imperative and Object Oriented backgrounds. I do believe that FP comes with paradigms that every programmer has to know these days3.

As an exercise, do you know what filter_map(|e| e.ok()) does? I did not, but my IDE told me on hovering above it. It is fancy code to say, remove all Error’ed elements.

Reading Words

let reader = BufReader::new(File::open(entry.into_path())?);
for line in reader.lines() {
    for word in line?.split_whitespace() {
        let w = word.to_lowercase().to_string();
        *counter.entry(w).or_insert(0) += 1;
    }
}

Note the two ? operators after the functions which can fail: File::open can fail and reading a line could fail. In case they fail, main returns early and the error message is shown to the user.

This is a pattern that takes some getting used to: *counter.entry(w).or_insert(0) += 1; We find counter.entry(w) or if that returns None (because the word has not been added yet), a 0 is inserted. The whole thing is dereferenced and incremented. Not difficult but definitely a bit of a stumbling block.

Sorting

The rest is straight forward and easy to understand in my eyes.

Like the other solutions, the HashMap is converted into a vector with tuple (word_count, word) as the elements. The vector is then sorted. 4

let mut tops: Vec<_> = counter.iter().map(|(w, c)| (c, w)).collect();
tops.sort_by_key(|(&c, w)| (std::cmp::Reverse(c), *w));

for (c, w) in tops.iter().take(10) {
    println!("{} - {}", w, c);
}

The only thing of note, is that I struggled writing the right key closure. tops.sort_by_key(|(&c, w)| (std::cmp::Reverse(c), *w)); Note, my use of &c and *w. Not only did I struggle with knowing where the references are but also with a lifetime error. IDE support definitely helped here5.

Summary

In conclusion, this was a fun little exercise. It is well known that Rust targets writing CLI apps. And it does so well on this word counting exercise.

I definitely do not think that Rust is any prettier than the C++ or the Go version. A cursory look tells me that it might be the shortest solution 6. But I doubt if pure line count should ever matter. When I first started reading Rust, I definitely had to get used to some of the concepts. And Rust is by no means an easy language. Yet, once you get used to it, writing something like this goes quickly and with confidence that the result is correct.

Update: Read the next post in this series, where I try it in Swift. And finally, read me going back and improving the original C++ version.


  1. Showing a disappointing lack of creativity it is just called the question mark operator. ↩︎

  2. A typical example is when creating a vector from a .collect() call. In that case, the compiler does not know into which container type the iterator should be collected. let v: Vec<_> = 0..10.iter().collect(); ↩︎

  3. This is written from an OO perspective. I am fully aware that FP has been practiced for decades by a large number of programmers. My point is: Everyone must know about map, filter and predicate-functions. ↩︎

  4. C++ has here the benefit of std::partial_sort, which neither Go nor Rust have out of the box. ↩︎

  5. Please let me know if there’s a more elegant way of sprinkling & and * on this. ↩︎

  6. Bad news for all of us paid by number of lines. ↩︎

Open article page →

Sentry and C++

If your program is running on more than one machine or is used by others, you probably want to get some insight into when things fail. I believe this is commonly called “Crash Reporting”. Such a crash reporting system will consist of a component to collect individual incidents and of a component to aggregate …

Read full article Collapse article : Sentry and C++

Crash Reporting

If your program is running on more than one machine or is used by others, you probably want to get some insight into when things fail. I believe this is commonly called “Crash Reporting”.

Such a crash reporting system will consist of a component to collect individual incidents and of a component to aggregate individual reports. For example, it will group common incidents by stack trace.

One public example of this, is Mozilla’s system (Socorro). Have a look here for statistics on all of Mozilla’s projects. Or here, for just the top ten Firefox crashes from a specific version:

Top 10 Firefox Crashes

The Top 10 Firefox Crashes

I don’t want to run my own server infrastructure, and have been using Sentry. Sentry is a SaaS offering for crash reporting and analytics1. Sentry has been a breeze to use. It is free for single-user projects and I have been playing around with it for some time with Python, Rust and React.

Unfortunately, with C++ I have been stuck. Sentry.io provides Sentry-Native which is essentially a C-style library. I’ve tried a few times to get it working and failed. However, last Friday I found crow, which is a C++ library for Sentry.

An example

#include <crow/crow.hpp>

int main(void) {
  nlohmann::crow sentry("https://7c164e487bc24a0fadb32c461fc71764@sentry.io/1860700");
  sentry.capture_message("Hello, Sentry!");

  printf("Hello, World!\n");
}

For your own project, you want to replace the project ID and the public key. Otherwise, your crash reports will go to me.

If we check on Sentry, we’ll see the issue show up here:

Our issue on Sentry

The issue we just caused shows up on Sentry.

I’ve put the code on Github for your convenience: https://github.com/siedentop/sentry_cpp_examples.

Please let me know your feedback on Twitter.


  1. There’s also Backtrace.io. If you work for Backtrace.io, please openly publish your pricing structure (I found it in your FAQ through Google: it starts at $99 per month.). Also, please have a free tier to let developers test your service. (And no, your 30-day trial is not good enough.) ↩︎

Open article page →

Nushell vs Bash

After last week’s post on how Nushell can be used to convert unstructured data to structured data, I wondered how I would approach the task using traditional tooling. I wrote ‘Bash’ in the title, but what I precicesley mean is POSIX pipes and command line utilities typically found on a Unix-like environment (Linux, …

Read full article Collapse article : Nushell vs Bash

After last week’s post on how Nushell can be used to convert unstructured data to structured data, I wondered how I would approach the task using traditional tooling. I wrote ‘Bash’ in the title, but what I precicesley mean is POSIX pipes and command line utilities typically found on a Unix-like environment (Linux, macOS, etc).

Again, the task is to convert weirdly structured text output (from sshping) to JSON for further processing or long term storage. For example, I might set up a cronjob to run analytics for my SSH connectivity. The results would be handy to have in JSON for later statistics.

The output format is colon-deliminated with lots of whitespace:

ssh-Login-Time:               1.83  s
Minimum-Latency:              1.81 ms
...
Download-Size:               8.00 MB
Download-Rate:               7.05 MB/s

My search brings me to the jo utility. Very nice and simple. Installation is easy on all supported platforms. I used homebrew. Note that there are also Node.js, Golang and Rust implementations available. I tried the Rust version and it worked fine but offered no benefit over the original, so I stuck with that.

First, jo expects inputs to have ‘=’ as the delimiter. But the input uses ‘:’ as the delimiter. The -d option did not seem to make a difference, so I resorted to sed to change the delimiter:

> cat ping.raw \
| sed -e 's/\:/=/' \
| jo
{"ssh-Login-Time":"               1.83  s",
"Minimum-Latency":"              1.81 ms",
...
"Download-Size":"               8.00 MB",
"Download-Rate":"               7.05 MB/s"}

Trimming the whitespace took the longest for me. I knew that jq is a useful command line utility for JSON data, so that’s where I looked. I also took a look at awk but the solutions all seemed that they required saving as a script, and I was looking for a one-liner1.

jq let’s you iterate over values in dictionaries using map_values and text replacement can be done using sub. I combined this to strip leading whitespace with this: jq 'map_values(sub("^[[:space:]]+"; ""))'

> cat ping.raw \
  | sed -e 's/\:/=/' \
  | jo \
  | jq 'map_values(sub("^[[:space:]]+"; ""))'
{
  "ssh-Login-Time": "1.83  s",
  "Minimum-Latency": "1.81 ms",
  "Median-Latency": "3.18 ms",
  "Average-Latency": "3.32 ms",
  "Average-Deviation": "987 us",
  "Maximum-Latency": "9.77 ms",
  "Echo-Count": "1.00 kB",
  "Upload-Size": "8.00 MB",
  "Upload-Rate": "16.0 MB/s",
  "Download-Size": "8.00 MB",
  "Download-Rate": "7.05 MB/s"
}

I then realized (after spending all that time getting jq to trim whitespace) that I could have used sed for this, too.

> cat ping.raw \
  | sed -e 's/:[[:space:]]*/=/' \
  | jo

Interpretation

I would say the “Bash” version is pretty okay. It took me longer to write than it should have. This is because I spend a lot of time figuring out a way to get jq to clean up the whitespace. I will admit that this is not really using Bash and that it sticks to traditional POSIX tools. I use two tools that you would have to install: jq and jo.

For reference, here is the Nushell version:

> open ping.raw | lines | split-column ':' metric value | str value --trim | save ping.json

And here is the Bash version:

> cat ping.raw \
  | sed -e 's/:[[:space:]]*/=/' \
  | jo

Comparing it to the Nushell version, I like that I can make it more readable by splitting it into multiple lines.

I find the Nushell version much easier to understand in a glance. For example, since jo is new to me, I doubt I will remember what it does in a week’s time. And the regular expression passed to sed is very readable – for a regular expression.

Challenge – Pure POSIX

Can I do this while sticking only to traditional command line tools?

After an hour, I came up with something which works. But this is how I felt about AWK:

Here is my AWK script in all its glory:

> cat ping.raw | awk '
  BEGIN {
       FS = ":[[:space:]]+";  # FileSeparator is ':\s+'
       print "\{";            # Start a JSON dict with '{'
    };
    {
    # Print ', "<key>": "<value>"', except for the first line,
    # where 'sep' will still be empty.
    printf "%s\"%s\": \"%s\"\n",
           sep, $1, $2
    sep = ", "  # Set 'sep' after the first line.
  }
  END { print "\}" }  # Close the JSON dict with '}'
'

I think that doing this task in AWK is an abomination2. It is readable only if you are very familiar with AWK (and I’d say my comments help). It took me also ages to write. And it is the wrong approach – I should not be hand-wrangling strings to write to a common format. Finally, it is also quite verbose. The only positive aspect is that it will work on any machine without any dependencies.

Conclusion

My ranking of the various solutions is this:

  1. Nushell
  2. POSIX pipes + sed + jo + jq
  3. …
  4. …
  5. Wait for it …
  6. …
  7. AWK

Nu is easier and offers more than sed + jo + jq solution. It is easy to save it not as JSON but as YAML or TOML or any other format. It is also very easy to do a bit of processing along the way. But the sed + jo + jq solution is also good enough for me. It does not require a new shell, and will be familiar to more people.

References:


  1. I am sure that there is a way to do it in one-line. It is just that I did not find that solution immediately. Feel free to let me know on Twitter what it is, and I’ll update the post. ↩︎

  2. Note, that I am not using AWK to parse JSON just to generate it. It is still a pain. ↩︎

Open article page →

Page 1 of 2