-
Notifications
You must be signed in to change notification settings - Fork 0
/
aoc2023-first-days.html
89 lines (89 loc) · 8.03 KB
/
aoc2023-first-days.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8"/>
<meta name="author" content="Nikita Sivukhin"/>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Zero allocation hello world in Rust</title>
<link rel="stylesheet" href="/static/style.css">
</head>
<body>
<div class="page">
<div class="meta">
<header>
<h2><a href="/">naming is hard</a></h2>
</header>
</div>
<div class="article">
<section id="Zero-allocation-hello-world-in-Rust">
<a class="heading-anchor" href="#Zero-allocation-hello-world-in-Rust"><h1 date="2023/12/02" hide="true">Zero allocation hello world in Rust</h1>
</a><p>This year of <a href="https://adventofcode.com">Advent of Code</a> I decided to try <a href="https://www.rust-lang.org/"><strong>Rust</strong></a>. I’m complete newbie and still learning basic concepts of language (btw, <a href="https://rust-book.cs.brown.edu">Brown Book</a> is amazing), but there were one idea that I wanted to try for the AoC challenges - I need to implement <strong>zero allocation</strong> solutions (at least for the first ones)!</p>
<p>What does it mean, <strong>zero allocation</strong>? Rust Book has nice <a href="https://rust-book.cs.brown.edu/ch04-01-what-is-ownership.html">chapter about ownership</a> which describes such concepts like memory, <em>stack</em> and <em>heap</em>. In short, your program usually operating with memory from two regions:</p>
<p>…something about zero allocations…</p>
<p>How can we analyze allocations of our program? I found nice tool <a href="https://github.com/matt-kimball/allocscope">allocscope</a> which record all allocations made with <code>malloc</code> in your program and allow you to analyze source of that allocations. Also, you can compile simple C code in shared library in order to override default <code>malloc</code> and add some debug information to it:</p>
<pre class="language-c"><code><span class="macro">#define</span> _<span class="identifier">GNU_SOURCE</span> <span class="number">1</span></code>
<code><span class="macro">#include</span> <span class="string">"stdlib.h"</span></code>
<code><span class="macro">#include</span> <span class="string">"stdio.h"</span></code>
<code><span class="macro">#include</span> <span class="string">"dlfcn.h"</span></code>
<code><span class="keyword">void</span>* <span class="function">malloc</span>(<span class="identifier">size_t</span> <span class="identifier">s</span>) {</code>
<code> <span class="keyword">void</span>* (*<span class="identifier">orig_malloc</span>)(<span class="identifier">size_t</span>) = <span class="function">dlsym</span>(<span class="identifier">RTLD_NEXT</span>, <span class="string">"malloc"</span>);</code>
<code> <span class="function">fprintf</span>(<span class="identifier">stderr</span>, "<span class="identifier">malloc</span>: %<span class="identifier">ld</span>\<span class="identifier">n</span>", <span class="identifier">s</span>);</code>
<code> <span class="keyword">return</span> <span class="function">orig_malloc</span>(<span class="identifier">s</span>);</code>
<code>}</code>
</pre>
<p>Let’s look at all <code>malloc</code> allocations in simple hello world program:</p>
<pre class="language-rust"><code><span class="keyword">fn</span> <span class="function">main</span>() { <span class="identifier">println</span>!(<span class="string">"Hello, world!"</span>); }</code>
</pre>
<pre class="language-shell"><code><span class="command">$> rustc main.rs</span></code>
<code><span class="command">$> LD_PRELOAD=./libm.so ./main</span></code>
<code>malloc: 472</code>
<code>malloc: 120</code>
<code>malloc: 1024</code>
<code>malloc: 5</code>
<code>malloc: 48</code>
<code>malloc: 1024</code>
<code>Hello, world!</code>
</pre>
<p>Wow, we are allocating 2693 bytes for simple hello world program! This is a bit unexpected - where all these allocations come from?</p>
<p>Couple of them looks pretty suspicious: 1024 bytes allocations is almost surely used for some intermediate buffers. We are printing string to the console - so most likely that Rust implementation of writes to <code>stdout</code> uses buffering for performance.</p>
<p>If we will unwind all macros we should get some code equivalent to the <code>write_all</code> call on <code>stdout()</code> stream: <code>io::stdout().write_all(b"Hello, World!")</code>.</p>
<p>We can look up for the code of <code>io</code> module and indeed see, that <a href="https://doc.rust-lang.org/src/std/io/stdio.rs.html#614"><code>stdout()</code></a> creates synchronized instance wrapped with <a href="https://doc.rust-lang.org/src/std/io/buffered/linewriter.rs.html#87"><code>LineWriter</code></a> which has default buffer size of 1KiB.</p>
<pre class="language-rust"><code>#[<span class="identifier">must_use</span>]</code>
<code>#[<span class="function">stable</span>(<span class="identifier">feature</span> = <span class="string">"rust1"</span>, <span class="identifier">since</span> = <span class="string">"1.0.0"</span>)]</code>
<code><span class="keyword">pub</span> <span class="keyword">fn</span> <span class="function">stdout</span>() -> <span class="identifier">Stdout</span> {</code>
<code> <span class="identifier">Stdout</span> {</code>
<code> <span class="identifier">inner</span>: <span class="identifier">STDOUT</span></code>
<code> .<span class="function">get_or_init</span>(|| <span class="identifier">ReentrantMutex</span>::<span class="function">new</span>(<span class="identifier">RefCell</span>::<span class="function">new</span>(<span class="identifier">LineWriter</span>::<span class="function">new</span>(<span class="function">stdout_raw</span>())))),</code>
<code> }</code>
<code>}</code>
<code></code>
<code><span class="keyword">impl</span><<span class="identifier">W</span>: <span class="identifier">Write</span>> <span class="identifier">LineWriter</span><<span class="identifier">W</span>> {</code>
<code> #[<span class="function">stable</span>(<span class="identifier">feature</span> = <span class="string">"rust1"</span>, <span class="identifier">since</span> = <span class="string">"1.0.0"</span>)]</code>
<code> <span class="keyword">pub</span> <span class="keyword">fn</span> <span class="function">new</span>(<span class="identifier">inner</span>: <span class="identifier">W</span>) -> <span class="identifier">LineWriter</span><<span class="identifier">W</span>> {</code>
<code> <span class="comment">// Lines typically aren't that long, don't use a giant buffer</span></code>
<code> <span class="identifier">LineWriter</span>::<span class="function">with_capacity</span>(<span class="number">1024</span>, <span class="identifier">inner</span>)</code>
<code> }</code>
<code>}</code>
</pre>
<p>Ok, let’s get rid of the <code>stdout</code> then and use <code>stderr</code> which also creates synchronized instance but without any additional buffering. We can write to <code>stderr</code> explicitly or use <code>eprintln!</code> macro for the same purpose. Let’s see how much memory we allocate in this case in our new program:</p>
<pre class="language-rust"><code><span class="keyword">fn</span> <span class="function">main</span>() { <span class="identifier">eprintln</span>!(<span class="string">"Hello, world!"</span>); }</code>
</pre>
<pre class="language-shell"><code><span class="command">$> rustc main.rs</span></code>
<code><span class="command">$> LD_PRELOAD=./libm.so ./main</span></code>
<code>malloc: 472</code>
<code>malloc: 120</code>
<code>malloc: 1024</code>
<code>malloc: 5</code>
<code>malloc: 48</code>
<code>Hello, World!</code>
</pre>
<p>Yes, nice! We reduced allocated memory to the 1669 bytes - which is exactly 1024 bytes less than our previous version.</p>
</section>
</div>
<hr/>
<div class="footer">
<p><a href="https://github.com/sivukhin/sivukhin.github.io">github link</a> (made with <a href="https://github.com/sivukhin/godjot">godjot</a> and <a href="https://github.com/sivukhin/gopeg">gopeg</a>)</p>
</div>
</div>
</body>
</html>