The lazy guy channel

2021-10-13 13:52:45 http://joeduffyblog.com/2015/11/03/blogging-about-midori/

Progress in mainstream operating systems design seems to be stalled. The world has settled on unix-like design from 50 years ago. More than 10 years ago Microsoft Research tried to design a “safe-and-secure-by-construction” OS - Midori. The project has predictably failed but it had quite a few correct ideas which are slowly moving into mainstream languages and operating systems. The series of blog posts behind the link describes the key design and implementation details of the project.

Here are the 3 most notable things which were pioneered in that project and became mainstream by now:
1. Midori was programmed in a language which prevents any kind of data races and invalid memory access by design. Rust is gaining momentum making the same promises.
2. All OS operations were asynchronous by default and the language had first class support for async/await. C# (the first mainstream language to implement first-class async support) borrowed this feature from Midori. Nowadays all languages are expected to support async programming style. io_uring on the other hand is slowly turning Linux into an async-first OS.
3. Since OS was written in a safe language, arbitrary code could easily be injected at various points in kernel without compromise of security or stability. Linux is slowly gaining the same feature in a limited form with eBPF. Open / Comment

2021-01-26 12:32:57 I am immersed into enterprise software world with its kingdom of nouns. It is an extreme verbosity in programming which is quite tiresome. But there is another extreme – the tense programming style of APL and its descendants (A+, J, K etc). Programs in these languages look like maths formulas. These languages pioneered the array programming language design long before it hit mainstream with NumPy. Well, APL stands for “array programming language” so it is no surprise that it is not based around scalar operations.

Anyway, I never found myself brave enough to learn and/or understand this style of programming. But I admire that people writing implementation for these languages transfer this style of programming to C (in which interpreters are typically written) which makes it some weird DSL. At first it seems unreadable, but it just needs careful reading (as opposed to skimming that we usually use to “read” code). K interpreter famously said to fit into 26 files named a.c … z.c, 80x24 each.

Here’s an example analysis of snippet of code that served as prototype for J language: https://zserge.com/posts/j/

A little more interesting example is the buddy memory allocator from A+ programming language: https://github.com/tavmem/buddy/blob/master/a/b.c

That contains 2 implementations: original 10-line in terse-style and rewritten in a more conventional style 700-line version. Though it is not a fair comparison because 700-line version also implements the combining of neighbouring segments and is massively commented. It is still fascinating that a real memory allocator that was used in production in one of the largest banks in the world can be written in 10 lines of code.

These snippets of code (as well as code in A+/J/K itself) steal the title of write-only programming language from Perl in my opinion. Open / Comment

2021-01-16 15:08:10 https://cp4space.hatsya.com/2021/01/08/the-neural-network-of-the-stockfish-chess-engine/

I’ve stumbled on a description of (extremely simple) NNUE neural network architecture used in current strongest chess engine – Stockfish 13. This is interesting because in 2017 Stockfish was beaten by Google’s AlphaZero and the time it seemed that chess is “solved” and deep neural nets are the future of board games. But that was not an actual end of story.

Since then, AlphaZero paper has been implemented in open source Leela Zero chess engine and Stockfish continued to steadily increase. So, these two are competing with various success for the first place in top chess engine championship for the last 7 seasons. And it really is very interesting which approach is better – “classic” brute-force like approach which evaluates tens of millions of positions per move using shallow network or “modern” Monte Carlo tree search which evaluates tens of thousands of positions using very deep network. It is not clear at all.

As a side note – both Stockfish and Leela chess are opensource and feature very high-quality C++ code – both readable and very performant (a rare combination). Very recommended reading if you write C++ for living.

Useful links.
[1] Last top chess engine championship results: https://en.wikipedia.org/wiki/Top_Chess_Engine_Championship#Tournament_results_(TCEC)
[2] Stockfish source: https://github.com/official-stockfish/Stockfish
[3] lc0 source: https://github.com/LeelaChessZero/lc0 Open / Comment

2020-11-26 13:05:07 http://www.stuartcheshire.org/papers/NagleDelayedAck/

If you have never been bitten by Naggle’s algorithm and Delayed ACKs then you probably have never written latency-sensitive low-level networking code. A good explanation of how two good ideas on their own can lead to subpar performance when combined. Open / Comment

2020-10-15 13:33:22 http://blog.moertel.com/posts/2013-12-14-great-old-timey-game-programming-hack.html

A nice write up on low-level optimizations on outdated architectures. Now in the world of SIMD, vector instructions and dedicated hardware it is only of historical interest. But still highly entertaining. Learning do put data in a way that is friendly to SIMD-algorithms is a similar skill that is relevant in modern times for a lot of low-level performance-critical code, as exemplified by Swiss table design [1], or internals of many machine-learning libraries.

[1]

Open / Comment

2020-05-27 15:53:01 It’s been a while since I posted something in this channel. I will lower bar a little and just post things which I’ve found interesting recently.

http://andykeep.com/pubs/np-preprint.pdf - Describes a nano-pass framework for compiler construction. Idea is very simple – construct compiler as a series of many simple transformations that progressively convert code from higher to lower levels languages. Typical compiler has 1 to 4 intermediate code presentations. This paper proposes having as many representations (languages) as there are passes, and introduces a framework for convenient description of these languages. This idea works as proven by the best-performing open-source Scheme compiler.

http://smallcultfollowing.com/babysteps/blog/2017/01/26/lowering-rust-traits-to-logic/ - Describes how to encode (part of) Rust type system as logic propositions. This is cool because allows to replace a lot of ad hoc type-checking/inference code with a single generic algorithm. Using prolog(-ish) languages in PL-relate research was a thing for while now. It’s cool that industry compilers are moving in the same direction. https://github.com/rust-lang/chalk - more info on the topic of logic programming in/for Rust. Open / Comment

2020-03-17 23:26:56 Timeouts and asynchronous task timeouts are hard. C# folks came up with “CancellationToken” pattern. This was the best strategy that I have used personally so far. But today I’ve read about “cancel scopes” and they look like an awesome development of the concept. I hope one day this API will come to my language of choice (whatever that will be).
https://vorpus.org/blog/timeouts-and-cancellation-for-humans/

A neighbouring article in the same blog talk more about "structured concurrency" which relates to direct spawning threads/tasks in the same way "structured programming" relates to goto statements. https://vorpus.org/blog/notes-on-structured-concurrency-or-go-statement-considered-harmful/ Open / Comment

2020-02-10 14:04:34 A while ago linux introduced io_uring (https://kernel.dk/io_uring.pdf) interface for dealing with asynchronous I/O with minimal syscall overhead. Latest Linux kernels extend this API to support more and more non-I/O related syscalls in async manner. I advise to read about this API, it is at the same time ingeniously simple, smart, and efficient. And looks like this is a future of high-performance server applications.

It’s funny how Linux has essentially reinvented low-overhead asynchronous message-passing for doing syscalls. Something that microkernels had to invent ages ago to be somewhat competitive in performance with monolithic kernels.

Tangentially related. I guess, at least some of my readers are not aware of famous Tannenbaum-Torvalds debate. It is an entertaining read: https://groups.google.com/forum/#!topic/comp.os.minix/wlhw16QWltI%5B1-25%5D. Touching monolithic vs microkernel design. Open / Comment

2020-01-30 13:04:52 https://adamdrake.com/command-line-tools-can-be-235x-faster-than-your-hadoop-cluster.html

This is an old article that becomes even more significant in the age of 50-core machines with half-terabyte RAM for 7$/hour.

Modern computers are ridiculously powerful. We tend to forget that because all that power made them very forgiving to people using vastly ineffective algorithms. And it is so easy to reach out for “cloud” that people tend to do that without even thinking if it is possible to make their program a little more efficient. I see this every day at a BigCo where I work because cloud is essentially “free” for us. Until it is not.

Next time you think you need to make your data processing distributed, think again. If you are processing up to single terabytes of data, it is very likely that single server should be powerful enough to process it in reasonable time. If it isn’t, then you may be doing something wrong. Open / Comment

2020-01-27 14:44:42 A friend of mine has created a new channel on programming-related stuff (probably. There’s only 1 post so far). I tried to come up with good introduction and failed. So, I advise you to start following it immediately. Here it is: @LoadBearingNop Open / Comment