Beating C with one line of Brainfuck

https://kiwec.net/blog/posts/beating-c-with-brainfuck/

by pmontra • 7 years ago

567 86 7 years ago

kiwec.net

jpgvm• 7 years ago

I love how this blog only has this single post and it's dutifully tagged #shitpost.

Thanks for sharing, I got a good chuckle out of it.

mortdeus2• 7 years ago

well we all got to start somewhere i suppose. It looks like he's off to a good start and perhaps we got another coding horror in the making. One can hope right?

_pmf_• 7 years ago

and it's dutifully tagged #shitpost

This should be mandatory for all "beating X in Y lines of Z" format posts.

klyrs3• 7 years ago

Marvelous. Anybody got an optimizing malbolge compiler?

return_0e• 7 years ago

Not an optimising one (yet) but a safe implementation of a malbolge interpreter written in Rust, which can run malbolge programs. Just for fun.

https://github.com/return/malbolge

lilyball2• 7 years ago

Has anyone used Rust to write an interpreter for INTERCAL yet?

citronvert2• 7 years ago

À la première place, GG mec !

NilsIRL• 7 years ago

Generated C:

  #include <stdio.h>
  
  char mem[30000] = {  };
  
  #define OUTPUTS 0
  char outputs[OUTPUTS] = {  };
  
  int main() {
      char* ptr = mem + 0;
      fwrite(outputs, sizeof(char), OUTPUTS, stdout);
  
      ptr[2] = getchar();
      ++ptr[2];
      while (ptr[2]) {
          ptr[2] -= 11;
          while (ptr[2]) {
              ptr[2] -= 22;
              while (ptr[2]) {
                  ++ptr[3];
                  --ptr[1];
                  while (ptr[1]) {
                      ++*ptr;
                      ++ptr[1];
                  }
                  ptr[2] = 0;
              }
              ptr[2] = 0;
          }
          ptr[1] = 0;
          ptr[1] += ptr[3] * 1;
          ptr[3] = 0;
          ptr[2] = getchar();
          ++ptr[2];
      }
      ptr[1] = 0;
      ptr[3] += *ptr * 1;
      ptr[2] += *ptr * 1;
      *ptr = 0;
      *ptr += ptr[3] * 1;
      ptr[3] = 0;
      ++ptr[1];
      while (ptr[2]) {
          --ptr[1];
          while (ptr[2]) {
              ptr[3] += 10;
              while (ptr[2]) {
                  --ptr[2];
                  --ptr[3];
                  while (ptr[3]) {
                      ++ptr[4];
                      ptr += 3;
                  }
                  while (ptr[4]) {
                      ++ptr[4];
                      ptr[3] += ptr[4] * 1;
                      ptr[4] = 0;
                      ++ptr[5];
                      ptr += 3;
                  }
                  ptr -= 3;
              }
              ptr[3] = 8;
              ptr[2] += ptr[3] * 6;
              ptr[3] = 0;
              ptr[2] += ptr[4] * 1;
              ptr[4] = 0;
              ptr[3] += ptr[5] * 1;
              ptr[5] = 0;
              ++ptr;
          }
          ++ptr;
      }
      while (ptr[1]) {
          --ptr[1];
          ptr[3] += 8;
          ptr[2] += ptr[3] * 6;
          ptr[3] = 0;
          ptr += 2;
      }
      while (ptr[0]) {
          putchar(ptr[0]);
          *ptr = 0;
          --ptr;
      }
      ptr[1] += 10;
      putchar(ptr[1]);
  
      return 0;
  }

markus_zhang• 7 years ago

my eyes!

zabzonk3• 7 years ago

Note that:

    #define OUTPUTS 0
    char outputs[OUTPUTS] = {  };

is not valid C (or C++) - zero length arrays are not a thing in either language,

jacquesm7• 7 years ago

  (base) jam@jam-XPS-8500:~/svn/src/music/mp3tomidi$ cc -c -Wall x.c
  (base) jam@jam-XPS-8500:~/svn/src/music/mp3tomidi$ cat x.c

  #define OUTPUTS 0
  char outputs[OUTPUTS] = {  };

Looks like you're wrong about that; at least for GNU C. It's not official C but if it works and generates no warnings it will be used too.

Long HN thread about this subject:

https://news.ycombinator.com/item?id=11674374

Zero length arrays are one of those things that C is renowned and notorious for: something that is useful at times but unpredictable because it is flirting with undefined behavior.

I usually compare C with a Formula 1 race car. It works well as long as you don't cut too many corners and when you do you end up plastered all over the road.

shultays2• 7 years ago

what it is being used for? I can't figure what that fwrite part does

readingnews• 7 years ago

I wonder if Brainfuck wins by his 100th of a second since he already called a program with words.txt, and therefore it was already loaded into memory, thus saving just a slice of time, as it would already be in the cache.

re• 7 years ago

Could also be that their version of wc is doing Unicode-aware counting by default; it could be a lot faster with LANG=C set in the environment.

https://unix.stackexchange.com/a/96580

kiwec2• 7 years ago

For some reason, wc is even slower with LANG=C.

    cat words.txt | time wc -w
    13018291
    0.76 user 0.01 system 0:00.78 elapsed

That's on the default wc build of void linux, and not in a proper benchmark environment, but that's still strange.

yitchelle2• 7 years ago

To avoid the caching bias, I think a fairer test condition would be to use multiple files and do it over a number of times. The lowest average time would be the winner.

sharedfrog• 7 years ago

You can manually clear the cache:

`echo 3 | sudo tee /proc/sys/vm/drop_caches`

klyrs3• 7 years ago

For a #shitpost, one need only observe the fastest run of program A being faster than the slowest run of program B, to declare A is faster than B.

With a sufficiently powerful static evaluator, you could embed the input into the program and get an even faster runtime.

shakna3• 7 years ago

With a sufficiently powerful static evaluator, you could embed the input into the program and get an even faster runtime.

If you feel the need to cheat, you could do something like I used for dumb_cat [0] and dump the resulting executables into a cache somewhere.

[0] https://git.sr.ht/~shakna/dumb_cat

gberger• 7 years ago

But the file is loaded in cat, which isn't timed

icebraining• 7 years ago

But the timed program still has to wait for cat to load the file. Both programs are launched (almost) simultaneously by the shell.

JoshMcguigan• 7 years ago

Is the 85MB test file available? I wasn't able to find it. I'd like to test this result against nerve [0], a brainfuck to x86_64 asm compiler I wrote (like funkicrab, it is also written in Rust).

[0] https://github.com/JoshMcguigan/nerve

apankrat• 7 years ago

Same here.

bff [1] has no fancy assembly, not even a compiler, just some basic loop unrolling and jump precomputation, but I too wonder how it compares to wc.

[1] https://github.com/apankrat/bff/

-- edit --

Found words.txt with 466551 words, so replicating it 28 times gets it to the OP's test size. Bff is ~5x slower than 'wc -w' ... which is not unexpected, but still slightly disappointing.

https://github.com/dwyl/english-words/blob/master/words.txt?...

kiwec2• 7 years ago

After editing my code to use EOF == 0, I get :

    19.55 user 21.49 system 0:41.13 elapsed

However, you're using 8-bit cells, so the resulting word count is incorrect. In case you're wondering, the file was generated with :

    python3 -m faker -o words.txt text -r [large number] -s '\n'

nipxx• 7 years ago

file-cache and system load jitter. That's it.

newnewpdro• 7 years ago

Right, especially with there being only a single run of each, inconclusive.

jacquesm7• 7 years ago

Totally missing the joke.

yitchelle2• 7 years ago

The HN crowd gets the joke, they just don't laugh about it. :-)

jacquesm7• 7 years ago

Hilarious. Hopefully this will end the endless flood of 'Beating C' posts.

https://www.google.com/search?q=site%3Anews.ycombinator.com+...

rs23296008n1• 7 years ago

Beating a C brainfuck compiler in rust/d/etc in 3 2 1...

s_gourichon• 7 years ago

Given the humorous setup and experiment report, I would bet one second of my life that maybe the guy ran the test with a few random files passing by, and mentioned only the one that just happened to be slightly faster in brainfuck.

I think I got the joke, it had me chuckle anyway.

iRobbery• 7 years ago

85 mbyte for 0.01s, on a terabyte you could easily get a cup a coffee or tea :)

stackzero• 7 years ago

I want more articles like this.

boothby• 7 years ago

Look what you made me do!

https://github.com/boothby/repiet/#but-is-it-faster-than-c

throw_m239339• 7 years ago

Following on the recent “faster than wc” blogposts, I decided to end this fad once and for all, using the best language ever created : Brainfuck.

This "Go faster than C" post was a complete joke, one could very easily write a "C faster than C" the exact same way to prove the absurdity of an optimized implementation that does not do what the original program does.

lgeorget• 7 years ago

This blog post also does that actually since the Brainfuck code is transpiled to C.

justinator• 7 years ago

It seems we've beat the webserver serving this blog with one hug from HN.

andrewflnr• 7 years ago

Should have written the server in brainfuck, I guess.

paulddraper• 7 years ago

There must be way more people reading HN than I would think.

Here we are 7 hours after post, overloading it.

Suppose "overloading" this blog is a mere 2 requests/s.

Suppose that an entire 10% of people reading HN click on this link, and on average click on it twice.

Further suppose that the average "active" HN user reads HN 5 times a week.

That means there are 1,210,000 active HN readers.

ddalex• 7 years ago

Thanks for the math!

I did several estimations of How-Many-of-Us-are-Here and I got ~1M users by various methods (eg number of upvotes using Reddit engagement numbers), so I'll take your number with a happy confirmation bias.

spsful• 7 years ago

Can someone summarize the article/link? I can't view it.

ChrisSD• 7 years ago

Brainfuck is faster than C. You should use it for all new code where performance is critical.

gilbertmpanga12• 7 years ago

How about beating a whole C system with BrainCrap!

stiray3• 7 years ago

I love it!!!

It is a great parody on latest trends in "my favorite xy language is faster than 'c/c++", each time I see one of those, it sends shivers down my spine.

Your language, that was made in c/c++, can hardly be faster than the language it was written in. Whatever optimizations it has, you can still make them in c/c++ with enough knowlidge, but probably you can optimize it some more (staring at c++ template metaprogramming) or use __asm or execute opcodes directly (cheating :D) The only question here is how good can the "compiler" be in making optimal cpu instructions from "your" language.

Stop this evangelist wars, your language can be great due to some other features (ease of use, knowlidge needed to be proficient in it, forgiveness of mistakes,..), you dont need to compare it to c/c++. It just doesnt make any sense.

tutfbhuf• 7 years ago

The only question here is how good can the "compiler" be in making optimal cpu instructions from "your" language.
Stop this evangelist wars.

I think if there is any need for a war at all, then it should be between compilers not languages.

randomsearch3• 7 years ago

Your language, that was made in c/c++, can hardly be faster than the language it was written in

What if the language you wrote includes a run-time that does JIT?

IcePic• 7 years ago

and the JIT is written in...

stiray3• 7 years ago

This would be "equivalent" but as jit has to process it first (overhead) and code here is just executing binary code, it will be faster. I am not talking here about readability, how much knowlidge is behind etc.

#include <unistd.h> char code[] = "\x01\xb8\x00\x00\xbb\x00\x00\x2a\x00\x00\x80\xcd\x00";

int main(int argc, char argv) { int (func)(); func = (int ()()) code; (int)(*func)();

return 0; }

This whole sharade of how fast the language is a nonsense. There are other metrics that are more important TODAY, the industry needs languages that are maintainable, can be used by cheap workforce that is simple to find anywhere and dont need to know much about computers, memory,... but rather about a problem. Why picking on c/c++ which is not solving any of those problems is such a trendy topic today, is beyond my understanding.

Athas• 7 years ago

Stop this evangelist wars, your language can be great due to some other features (ease of use, knowlidge needed to be proficient in it, forgiveness of mistakes,..), you dont need to compare it to c/c++. It just doesnt make any sense.

What if the purpose of the language is exactly to be faster than reasonably written C? Then a comparison makes sense.

Also, I have written a language that is "faster than C" in a certain naive sense, and it was not written in C. It does generate C, but not the kind of C sane humans like to write.

That does not mean those wc comparisons are indicative of real performance, though. They are just meant as provocative ways to get attention.

mortdeus2• 7 years ago

"Your language, that was made in c/c++..."

What's funny is that C was initially written in B, and C smoked the living hell out of that language. As it turns out, the speed of compiled code and the running time performance of compilation is two drastically different things.

If C++ was a runtime language it would be slower than a checkout line at Walmart filled with grandma's trying to get in the last bit of Christmas shopping after all of them had just found out their kids are finally going to come out and bring their grand babies to visit for the first time after all these years.

In other words, the way you measure speed and the way I measure speed are to different things. If you had to account for the time it took to grow food back in the old days when accounting for how long it takes you to make dinner, you could say that standing behind a line of grandmas is way quicker.

But both realities are not only mutually exclusive but if you were to ask me; one of those two situations is more gratifying and the other is absolutely aggravating.

Waiting on C++ to compile feels like waiting on a line of grandmas at walmart just so I can get something to eat.

naikrovek2• 7 years ago

Your language, that was made in c/c++, can hardly be faster than the language it was written in.

It doesn't work that way.

imtringued• 7 years ago

Your language, that was made in c/c++, can hardly be faster than the language it was written in.

You're making the mistake of associating the performance of a program to be purely be a product of the language. It is not difficult to write inefficient code in any language.

judofyr• 7 years ago

Since cells need to be 32-bit for counting more than 255 words, you’ll also need to replace the few occurrences of char to int.

Well, part of the fun of Brainfuck is working around the limit of 8-bit cell size. How about creating a version which implements 32-bit numbers by storing them in four cells?

jangid• 7 years ago

Will rust be any faster? Like 'ripgrep'.

DarkCrusader2• 7 years ago

Here you go. https://medium.com/@martinmroz/beating-c-with-120-lines-of-r...

shultays2• 7 years ago

I think that BF implementation uses 32bit cells (which is not standard BF?)

classified• 7 years ago

If you're going to "beat" C with another language, it will obviously be one that compiles to C.

Beating C with one line of Brainfuck

Related Stories