If I wrap things in a function and run it a second time in the repl, this is what I get:

    $ JULIA_LLVM_ARGS="-unroll-threshold=500" ~/julia-b00e9f0bac/bin/julia -O3 --check-bounds=no

    julia> include("nbody.jl")
    run (generic function with 1 method)

    julia> @time run(50000000)
    -0.169075164
    -0.169059907
    2.044478 seconds (294.25 k allocations: 12.599 MiB, 8.89% compilation time)

    julia> @time run(50000000)
    -0.169075164
    -0.169059907
    1.867936 seconds (12 allocations: 1.750 KiB)

Basically, it's toy programs written in each of these languages. They measure how fast each one is executed. This methodology does have it's limitations, which that page is upfront about.

You are correct that the C feature is often banned. Rust doesn’t even support it at all.

C is a tricky beast to tame.

One library I have exploits the fact that D templates are embarrassingly better than C++'s, so you can actually benchmark a template against it's parameters in a clean manner without overhead - that could be anything from a size_t parameter for a sort or a datastructure for example.

        enum cpuidRange = iota(1, 10).map!(ctfeRepeater).array;
        @TemplateBenchmark!(0, cpuidRange) 
        @FunctionBenchmark!("Measure", iota(1, 10), (_) => [1, 2, 3, 4])(meas) 
        static int sum(string asmLine)(inout int[] input)
        {
            int tmp;
            foreach (i; input)
            {
                tmp += i;
                mixin("asm { ", asmLine, ";}");
            }
            return tmp;
        }

edit: https://github.com/maxhaton/chimpfella - I haven't bothered to add pmc support yet

What is "real theorem-proving language" in this context? ATS has ATS/LF that is designed for writing formal proofs in the language.

http://ats-lang.sourceforge.net/DOCUMENT/INT2PROGINATS/HTML/...

But when using that variant all the correctness guarantees that Haskell is known for are no longer on the table.

Because of that, it is usually pretty easy to substitute an optimized algorithm or a container for another one with minimal code changes. In C, because there is no standard for how to do containers and algorithms, it is likely that every library does something a little different in terms of conventions making it harder to swap in implementations.

I have no problem doing that if I need to. But it feels like I'm fighting against the grain of rust more than I'd like.

I'd either start at a query entry point, or find the email delivery path or something. Or skim through the files and see if anything catches your eye. Or invent a question for yourself - how does X work (for some X), and see if you can find that part of the code.

Wherever you start, explore around a bit then go deep. See if you can understand for yourself how some small, interesting part works (by tracing out the various structs and function calls). Understanding how the whole program fits together is a separate skill - but don't worry too much about it.

Personally I fell in love with the code in src/lib/memarea and mempool. The way dovecot handles memory pools is super clever. There's also lots of src/lib-X directories, and they're reasonably self contained if you want to skim that list and find something more focussed.

If you haven't read much code before and dovecot feels too big and scary, start with something smaller. I can also recommend reading the sourcecode for git or the code for redis. Oh, and if you do, do yourself a favour and checkout one of the earlier versions of those projects. The lines added early in a project's life are usually more succinct and important compared to lines added later on. So earlier versions are usually better reads. When I read redis, I think I read the code for redis 2.0 or something.

When this is done, the compiler can inline qsort, and replace the indirect function call with an inlined version of intcmp, and then things are equivalent.

In that case, the compiler could make a specialized qsort using intcmp automatically.

https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

It looks like the autovectorizer did a really good job on this one.

This blog post shows how to write simple idiomatic Rust code that will allow the compiler to auto-vectorize:

http://cliffle.com/p/dangerust/6/

The remaining work _on this particular benchmark_ is the regex algorithm itself. I'm on mobile so I can't do a deep dive, but I haven't yet figured out how to easily improve on this particular case. It has to do with the fact that the benchmark has a high match count and the finite automata approach in the regex crate has a bit higher overhead than the typical backtracking solution used in PCRE2 (which is also JIT'd in this case).

It's not the language, compiler, inlining or any other such thing. It's algorithms.

But this is one single benchmark. Before regex-redux there was regex-dna, and Rust's regex crate was #1 there. Why? Same reason. Algorithms.

You can't judge regex performance by a single benchmark. Two won't do it. Not even ten. It's one of the many problems with the Benchmark Game. This would be fine if everyone was circumspect and careful with their interpretation of the data provided, but they aren't. And the Benchmark Game doesn't really do much to alleviate this other than some perfunctory blurbs in some corners of the web site.

With that said, running a benchmark is hard work. It's easy to criticize.

You get a null terminated char array but the length is actually available since arrays (as long as they haven't decayed into pointers) can still share their length at compile time.

While C++ isn't an exact superset of C it's close enough but it's not the point. The debate is about how the languages are used. Otherwise you could always say "yeah, use inline assembly and don't use any abstractions with the exception of structs, pointers and arrays".

>>Available C++ hash table libraries have benefit of overwhelmingly more optimization attention than could be afforded on behalf of a single program, and they deliver that performance to all dependent programs.

They are also general purpose. When you have something specific to optimize you will always beat general solutions.

>>Every programming project is an exercise in practical economics: your strictly-limited available attention goes where you choose. The greater productivity of coding in a more powerful language frees up attention that may then be allocated to areas that would otherwise suffer neglect.

Sure. The debate is about what is faster though and then C++ is not faster than C but C is often faster than even slightly idiomatic C++ and much faster than C++ with all the modern features used frequently. You will get stuff done faster in a higher level language of course but that besides the point of debate which language is faster where performance matters.

>>Whatever amount of attention you devote to making code in a poor language work at all, you may spend a fraction of coding in a better language, and the balance on other beneficial uses, such as better performance.

I don't agree C is a poor language. It's quite a common view as well. A lot of people who are good at low level stuff prefer C to C++ because the language is simple, easy to read and easy to reason about. C is poor at some things, it's fantastic for others. I personally love the language and it's my choice for many weekend projects.

>>That the new program is faster than the old program reliably demonstrates that the old program was not so well optimized as you suggest. (Your comment elsewhere, that "the whole project uses only [a] minimal set of C++ features" reveals perhaps more than you intended.) One may surmise that the old program's authors spent more of their limited attention on its effectiveness at playing chess than the latter program's author needed to.

Stockfish is a big decade+ old and still heavily developed community project with tens of programmers contributing to it. A lot of attention was given to it and to optimizing specific parts of it. Still, it's written in C++ in usual (although still very minimal) style and there is cost to it.

>>That the third, assembly-language program is faster still demonstrates that the previous programs left performance on the table.

Well, my experience is that people good at assembly run circles around very good C/C++ programmers. I would go as far as to say that it's hard to take anyone who doesn't realize it seriously. There is just so many things you can't do in C/C++ even with today very smart compilers.

>>My experience is that it is not hard to double the speed of a typical program just by paying attention to cache and pipeline effects. Most likely, the asm coder just happens to know more about those effects, knowledge that could as well have been applied to the others. Most programs seem fast enough exactly until another, faster one comes along; then they are instantly slow.

You just don't get it. Stockfish is a program which depends on being fast. Making it fast is the number one priority. A lot of very smart people spent hundreds of hours optimizing small parts of it like the best way to generate chess moves in as few CPU cycles as possible, designing the hash table to minimize cache misses etc.

If you can make Stockfish 2x faster you would be considered the prophet of programming and your statues would be raised in cities around the world. Seriously, it's not some average random code which you can make faster applying concept you happen to see on front page of Hacker News. We are talking about the code where performance matters. All the people working on such code know a lot about all the concepts you mentioned because they apply them day to day.

Anyway, CFish, asmFish and Stockfish are all open source projects. You can find them on Github. You can ask the authors why they think their stuff is faster if you are curious about it. I mean maybe it's worthwhile to understand why someone chooses to do all the work to re-write a popular community project to C or asm. It's a lot of difficult work. They might know something you don't.

Theoretically portable, maybe. But C is actually portable in practice - you can compile C code for the vast majority of CPUs and OSs.

FWIW I feel like this is a fairly recent (good!) development. Up through TR/TR1 I think at least half the C++ code I saw was pretty heavy on the "Java envy" and not at all concerned about the cost of dynamic dispatch or memory allocation. Avoiding vtables was derided as part of "C with classes" - today that usually refers more to templates and exceptions but STL implementations were not mature enough and too much code not exception-safe for those to be universally viable back then. Something I heard more than once was that if you had a destructor it should always be virtual just in case someone wanted to subclass it later.

Naturally we have to ignore that wxWidgets, Gtkmm, MFC, ATL, Qt, COM, DirectX, IO Kit, DriverKit, Skia are still around.

My experience is that C++ that's written for performance will often prefer the use of templates over inheritance since the cost is then paid upfront by the compiler. What's stopping a C programmer from hand-coding template instantiations (via macro or otherwise)?

That makes sense for video games. Recently I was goofing with cyrus-imap. I wanted to parse the emails out of an mbox file into JSON (JMAP). Parsing an email with cyrus currently does about 5-10k calls to malloc, but the objects are all extremely short lived - they just have to live long enough to parse and then convert to JSON. This is a perfect case for a bump allocator - I'd love to allocate all the parsed email fields into an arena and then clear the whole thing when we move on to the next message.

Yes, Cyrus uses a ton of its own internal structs for emails, and they're littered with strings and vectors. (Eg for email headers, lists of email recipients, plain text / HTML message content, etc).

Looks like bumpalo will do the job, since it implements its own Box, Vector and String. I understand why, but it seems jarring that I'd need to replace the data types in order to change out the allocator like this. I'm definitely keen for GAT landing if it means bumpalo and friends don't need to reinvent the world to be able to change the allocation strategy.

Edit: Oooh Vec::new_in is in nightly! Exciting! https://doc.rust-lang.org/beta/std/vec/struct.Vec.html#metho...

https://rust-lang.github.io/rfcs/1398-kinds-of-allocators.ht...

https://github.com/rust-lang/rust/issues/32838

https://github.com/rust-lang/wg-allocators

I wish there was a C/C++ compiler flag for treating all pointers as __restrict__. However I guess that C/C++ standard libraries wouldn't work with this compiler option (and therefore this compiler option wouldn't be useful in practice).

Does that also hold for a "uint8_t"--which is often just a renamed unsigned char rather than being a genuine type of its own?

To my knowledge there is no C compiler that promises to always handle all forms of UB consistently. The closest you could get would probably be something like Valgrind.

Use your brain and use your tools. C is not really that hard for a large number of problem sets.

If I recall correctly, the STL provides guarantees that prevents it from taking advantage of flat lists. I think some containers (not arrays) guarantee that they don't move the address of whatever they're containing, even if you insert or remove elements. Even if they switched to flat lists, it would be a flat list of pointers, with all the incurred overhead.

Likewise, I believe I have heard of small string optimisation being impossible with std::string for similar reasons.

When I changed the hardcoded node size from 136 to 1024 bytes, time went down from 3.6 secs to 2.6 secs on my laptop. It kind of plateaued at 1024 bytes. I didn't do more extensive testing.

What's the rationale for the choice of 136? A cache line is usually 64, so the CPU will always end up loading a multiple of that in any case.

When I did a rope implementation myself (I don't know how it compares in terms of performance) I think I ended up with nodes of 4096 or 8192 bytes size. That was based on a Red-black tree. When I load ~1Gig of data, even with a node size of 4096, there will still be 2^18 nodes, meaning each access requires sth. like 17 child traversals, which seems a lot to me. So I can't see myself going down to 200 bytes or less.

https://ridiculousfish.com/blog/posts/array.html

In the sense of swapping the underlying implementation as the number of items in the collection increases.

The number of people who dismiss the lowly array is way too high. Arrays are fast. Keep your data in the cache and they're 10x or more faster than normal, and plain flat arrays are almost always faster than literally any OOP nonsense. By "almost always" I mean that I've never once encountered a situation where flat arrays weren't the fastest solution attempted, and I haven't seen everything, so I can't claim they're always fastest.

People really don't understand how fast their computers really are, thanks to developers not caring how fast their code is.

Linear arrays are often faster, not because they require fewer memory loads, but because the cache has intelligence built in (the prefetcher) that loads some memory in advance even before the code requests it. That intelligence works way better with linear array scans than with pointer chasing. (I'm not sure if these loads will count as cache misses or not).

Most people who don't bother with that probably also don't bother with the performance of their hashmap.

Perhaps you'd like to take on that task?

> Require submissions to come with analysis.

Which raises the barrier for program contributors and presumably would require me to judge whether their analysis was acceptable? Me? Really? ;-)

> disclaimers on the web site more discoverable

The problem is that no one wants to "discover" disclaimers.

We want to see something that supports whatever it is we already believe — and we're very good at ignoring anything else.

Well Go and C#[1] still suffer from the billion dollar mistake (null pointers), which represents at least 1/3 of errors I've witnessed in JavaScript code, so I'd say they at best removes 70% of errors. And there's also logic errors, for which neither Go's or C#'s type system helps either, so maybe we're at 50% error reductions with Go and C# compared to JS and Python. I don't even think that Rust, with its really helpfull type system (ADT + Affine types) achieves 95% error reductions though.

[1]: for C#, at least last time I used it, which was 2011

-- How much usage do you expect to have? The more usage, the more important performance and correctness are.

-- How critical is your application? The more critical it is, the more important correctness is.

Also, the argument that you can spend developer time to increase correctness just by writing more tests works up to a point, but then it doesn't, because of diminishing returns. With Rust you can eliminate certain entire classes of bugs which tests will never reach.

I agree with your post generally though.

One quick example: standard-class objects in Lisp are mostly more dynamic than python objects[1] but structure-class objects are quite static, and compilers will use this to their advantage.

On top of this, functions in python are in fact objects; in python you can do this just fine:

  def foo():
    foo.bar = 3

  def bar():
    print(foo.bar)

If you read the Lisp specification you will see dozens of places where they allow for opting out of dynamism in ways that help the compiler optimize. Type declarations are one and the fact that a function defined in a single file is considered to have a fixed definition for the scope of the file is another.

1: It's not quite as easy to add new slots to Lisp standard-class instances on the fly as it is to python class instances, but it's doable, and Lisp, of course, supports class redefinition in a way that few other languages (including Python) do.

https://morepypy.blogspot.com/2011/04/tutorial-part-2-adding...

and you can always compare “equivalent” algorithms as some languages may not be able to efficiently express the same algorithm as another. i know what you are after, but trying to have some benchmark that is “fair” according to some spec that is important to your needs will just be seen as pointless to others. benchmark game at least lets us see what the performance ceiling is of various languages, and anytime you object to a language having a worse implementation you may go fix it.

i think what anyone with a clue understands is that C C++ and Rust all have roughly equivalent performance ceilings. Nobody really thinks Rust is faster than C now.

http://cm.bell-labs.co/who/dmr/chist.html

> Thompson was faced with a hardware environment cramped and spartan even for the time: the DEC PDP-7 on which he started in 1968 was a machine with 8K 18-bit words of memory and no software useful to him. While wanting to use a higher-level language, he wrote the original Unix system in PDP-7 assembler. At the start, he did not even program on the PDP-7 itself, but instead used a set of macros for the GEMAP assembler on a GE-635 machine. A postprocessor generated a paper tape readable by the PDP-7.

> Although we entertained occasional thoughts about implementing one of the major languages of the time like Fortran, PL/I, or Algol 68, such a project seemed hopelessly large for our resources: much simpler and smaller tools were called for. All these languages influenced our work, but it was more fun to do things on our own.

> By 1970, the Unix project had shown enough promise that we were able to acquire the new DEC PDP-11. The processor was among the first of its line delivered by DEC, and three months passed before its disk arrived. Making B programs run on it using the threaded technique required only writing the code fragments for the operators, and a simple assembler which I coded in B; soon, dc became the first interesting program to be tested, before any operating system, on our PDP-11. Almost as rapidly, still waiting for the disk, Thompson recoded the Unix kernel and some basic commands in PDP-11 assembly language. Of the 24K bytes of memory on the machine, the earliest PDP-11 Unix system used 12K bytes for the operating system, a tiny space for user programs, and the remainder as a RAM disk. This version was only for testing, not for real work; the machine marked time by enumerating closed knight's tours on chess boards of various sizes. Once its disk appeared, we quickly migrated to it after transliterating assembly-language commands to the PDP-11 dialect, and porting those already in B.

> By 1971, our miniature computer center was beginning to have users. We all wanted to create interesting software more easily. Using assembler was dreary enough that B, despite its performance problems, had been supplemented by a small library of useful service routines and was being used for more and more new programs. Among the more notable results of this period was Steve Johnson's first version of the yacc parser-generator [Johnson 79a].

> By early 1973, the essentials of modern C were complete. The language and compiler were strong enough to permit us to rewrite the Unix kernel for the PDP-11 in C during the summer of that year. (Thompson had made a brief attempt to produce a system coded in an early version of C—before structures—in 1972, but gave up the effort.)

What failed was the initial port attempt to C, not UNIX running on PDP-7.

While I am quite critic of C, I take the effort to learn and criticise properly, because regardless of my opinion it isn't going away on my lifetime and bills need to be paid.

Only for organizations where "devops" means "ops". If your organization practices continuous deployment, then getting a bug fix out is no big deal (merge your PR to master and make sure the deployment doesn't fail); certainly no devops time is required.

> Moving breakage to earlier in the developer cycle typically reduces the cost of fixing it.

This axiom originates in the days of waterfall development and annual software deployments shipped to customers on shrink-wrapped physical media. It's not nearly as costly as our dated CompSci or SoftEng educations make it out to be.

Your average web service isn't going to benefit on balance from moving from Go to Rust because any gains in finding/preventing bugs sooner are going to be dwarfed by the slowed pace of development.

Of course, someone will point out that data races of the sort that Rust precludes are really hard to debug, which is true, but they're also very rare because request handling rarely requires parallel access to local resources (mostly things like database connections, where the locking is handled by the database library). The total cost of dealing with these for your average web application is still going to be dwarfed by the smaller tax Rust imposes on every change you make.

Note that Rust has improved significantly, both by accepting more correct programs (laxer rules such as non-lexical lifetimes) and by improving tooling (rust analyzer). I'm not sure if they'll ever close the gap completely such that using Go/C#/etc are relegated to certain niche use cases, but I think it will continue to steal more and more of the application space that leans toward performance- or correctness-sensitive.

are you maybe thinking of iterators? you have to assume iterators are invalid after a move.

For analysis, it increases review time and increases the burden on contributors. The extent to which any one person can review all analyses isn't clear to me, and they would likely need to rely on contributors to self regulate them. But I would expect the maintainers to review them for some minimal level of quality. Being more specific than this would require a more thorough proposal. Given my time constraints and how much I dislike interacting with you, it's not something I can do right now.

As for increasing contributor barriers, yes, adding an analysis requirement would do that. However, I think you could compensate for that partially by reducing existing barriers. I've submitted code to your game before, and I'm unlikely to ever do it again. One reason is that interacting with you was unpleasant for me. But I found the interface difficult to navigate (that has since changed) and the rules difficult to discover. I think barriers could be reduced by switching to github (one of the reasons I use github) with more automated checks on submissions and better documented rules. (At the time when I worked on a submission it was unclear for example how to submit a Rust program that used external crates.)

Invariably though, providing an analysis is still more work. IMO, I think it would add rnough value to be worth it. I imagine many amalyses would build on top of others, similar to how code submissions do that today. As can be seen in any thread about the Benchmark Game, there are tons of comments that misunderstand things or make wild guesses. (Followed up invariably a day later with coy quips from you.) Some of those comments are from people that are unlikely to be helped by my analysis idea. But a lot aren't. I think a lot of people would benefit from an explanation of the performance characteristics of the program.

I generally try not to publish benchmarks without analysis. Here's one example.[1] I care a lot about it and I think it has immense benefits in terms of educating others. But reasonable people can disagree. You might have different values than me, which influences whether my suggestions are applicable to you or not.

As for the disclaimer, I don't really see the point of being more specific. There isn't much to this one? A simple suggestion might be to put it at the top of each page or even in the description of each benchmark. I don't know how much this would help things. Maybe people would still just ignore it.

People regularly misinterpret benchmarks and especially those in your Benchmark Game. From what I can tell, you as the maintainer have done very little to address that. Maybe you don't care. Maybe you think it isn't your problem to solve. Maybe you think it can't be solved or even improved, and therefore it isn't worth doing anything. I don't know. We might just disagree, which is fine.

Invariably, you can just respond and tell me to go do it. I think that's a cheap response, but I know you're fond of it. I've been thinking a lot about it and considering starting my own benchmark. But it will likely be a few years before I'll get to it. It is a trying daunting amount of work.

[1] - https://blog.burntsushi.net/ripgrep/