25 ms·

4B If Statements

• lmm 3y ago
  > Considering the computer has to read 40 GB of data from disk, map it to physical memory and then let the CPU has a rip of it No it doesn't? Maybe it needs to set up page tables for 40GB, but it doesn't need to read the parts you're not using into memory, that's part of the point of memory-mapping like this - it sets up a page fault handler to load the page into memory when accessed, rather than needing to do it all up-front.
  • DHowett 3y ago
    Given that the entire linear chain of comparisons (therefore, every instruction) needs to be evaluated for 2^32-1, it would indeed need to read and execute the entire 40GB file. The fact that it does so by faulting in each page before instructions in it can be executed doesn’t materially avoid having to read every byte. Clearly the author should have checked the larger numbers first to prevent this (:
    • Centigonal 3y ago
      Software development needs to be driven by user needs. Clearly the best action in this scenario is to bundle in telemetry code that reports back which numbers are used with this program, assemble a ranking of the most frequently compared numbers in the real world, and use that to order the comparisons in v2 of the program.
      • satiric 3y ago
        Of course the modern "scaleable" solution is to ask ChatGPT if the number is even or odd, and then print ChatGPT's response.
        • constantly 3y ago
          Using selenium and chrome webdriver under the hood to do so, as well.
      • chrismorgan 3y ago
        It’s worth noting that good compilers can actually do a version of this: it’s called profile-guided optimisation <https://en.wikipedia.org/wiki/Profile-guided_optimization https://en.wikipedia.org/wiki/Profile-guided_optimization>. Not many projects use it, because it’s generally a bit of a bother (build a special version, run your profiling, then build everything all over again), but Firefox gets good mileage out of it. My vague recollection is a typical sort of speedup of 5%.
      • eviks 3y ago
        Don't forget to remove the least used 1% of the numbers to make it leaner!
    • lmm 3y ago
      > Given that the entire linear chain of comparisons (therefore, every instruction) needs to be evaluated for 2^32-1, it would indeed need to read and execute the entire 40GB file. It does, but not step by step the way the part I quoted described - the reading from memory can be pipelined with the execution. (And it's an ideal access pattern - reading linearly once - so it wouldn't surprise me if other optimisations kicked in)
  • slabity 3y ago
    Did you ignore this part that came a bit before that? > I decided to map the file into the address space instead of reading all of it. By doing this, we can just pretend that the entire file is already in memory and let the poor OS deal with fitting a 40 GB blob into virtual memory. Why take a vaguely rhetorical statement and then complain it contradicts a more concretely accurate statement before it?
    • lmm 3y ago
      > Did you ignore this part that came a bit before that? No, just the opposite - I read that and that's exactly why I'm saying there was no need to read the whole thing into memory before starting to execute it. > Why take a vaguely rhetorical statement and then complain it contradicts a more concretely accurate statement before it? Because it's a contradiction in what they've written?
      • rocqua 3y ago
        The article doesn't state the entire program has to be read into memory before it starts executing. Instead the article states that during execution, for the highest inputs, the entire program needs to pass through memory for execution to finish.
  • rocqua 3y ago
    For the highest possible input, all of the program needs to be read into memory. Just not all of it at the same time. I guess technically most of the RET instructions are jumped over, and so they don't need to be in memory. But that isn't how cache-lines (let alone pages) work.
• Hugsun 3y ago
  Visionary genius Ross van der Gussom is my new favorite mythological creature.
  • punnerud 3y ago
    Think of Python as a way to script C, and skip most/all compiling. If your Python is slow, you are probably doing it wrong. Recommend reading this: https://cerfacs.fr/coop/fortran-vs-python https://cerfacs.fr/coop/fortran-vs-python
    • IshKebab 3y ago
      Not all Python is just a front-end to fast C code. That only really works with numerical computing of big tensors. Though I'd still agree - if your Python is slow you're doing it wrong - you shouldn't be using Python!
      • punnerud 3y ago
        If you switch away from Python, you are probably sub optimizing
        • eru 3y ago
          There are reasons other than speed that makes people move away from Python. Btw, recently CPython has sped up a lot. Between versions 3.9 to 3.12 many programs run about twice as fast. Much of that improvement is thanks to the 'faster-cpython' project (which Microsoft is generously funding). I contributed about a 1% speedup during that time, too.
      • eru 3y ago
        You can also call eg Rust or OCaml code from Python, doesn't have to be C.
        • IshKebab 3y ago
          Of course. When people talk about calling C from Python they really mean "a fast language".
• teaearlgraycold 3y ago
  > Now, in a world where AI is replacing programmers by the minute, taking their jobs and revolutionizing the way we think about code I’m dumb. This is a joke right? At most I can say AI has revolutionized how I interface with documentation.
  • ninepoints 3y ago
    I would think that the title alone should indicate that this entire bit is satire.
  • leosanchez 3y ago
    > This is a joke right? I hope so. If not, it is a load of bullshit.
  • coldtea 3y ago
    That is a joke in the context of the post. Not so much a joke in general reality. For you, AI might have just revolutionized how you "interface with documentation", but a huge share of programmers in any company are already using AI, officially or unofficially as a coding assistant. And of course MS, IntelliJ and others are all having out products on this.
    • teaearlgraycold 3y ago
      I’m using it as a coding assistant. The coding assistant is essentially fancy hyper speed documentation.
  • speedgoose 3y ago
    Would you spend a lot of time and money on contractors to do an often disappointing job, or ask a LLM to do a better job immediately?
  • elzbardico 3y ago
    GPT is a brilliant interface to github search and stack overflow. That's all. Most of the time I use it, like stack overflow, you need to double check if it is the idiomatic way of doing it, if it IS still the right way of doing stuff or even if the code is correct, not full of bugs or even if it is solving the right problem. It is like a helpful, but over-confident intern helping you with toil and research.
• satiric 3y ago
  Surely any solution that claims to be performant would use a binary search, rather than looping through every number. Would be a little trickier to generate the code though. Edit: /s of course
  • tarruda 3y ago
    I wouldn't touch the generated ifs, but would generate a b-tree database which maps integers to the address of the generated code which has the desired "if" comparison. Then the C program starts by querying the b-tree for the address and just assigns that to "isEven" pointer. Hmm... Nevermind. A really smart way to solve this would be to store the result of the "isEven" computation directly on the b-tree, so the whole problem can be solved with a simple database query!
    • neilv 3y ago
      Make it a microservice in Kubernetes so that it scales.
      • jiggawatts 3y ago
        I wouldn’t be surprised if there isn’t at least one thing this insane at some FAANG. “We’ve got to scale the maths engine cluster to handle the load!”
        • rplnt 3y ago
          I mean, there's this https://www.npmjs.com/package/is-even https://www.npmjs.com/package/is-even
          • vegardlarsen 3y ago
            The actual implementation of this package is even better. https://github.com/i-voted-for-trump/is-even/blob/master/index.js https://github.com/i-voted-for-trump/is-even/blob/master/ind...
• midjji 3y ago
  % is a surprisingly slow way to do so compared to x & 1.
  • Cyph0n 3y ago
    I’d assume any decent compiler would optimize a “% 2” (or any power of 2) into a bitwise op. Could be wrong though!
    • constantly 3y ago
      Easy enough to check with even the indecent compilers! https://godbolt.org/ https://godbolt.org/
    • roetlich 3y ago
      Tested it! In C: https://godbolt.org/z/7xTrhGasc https://godbolt.org/z/7xTrhGasc GCC uses &1 even using -O0. LLVM using -O0 still does the modulo, but at -O1 it does a clever &-2. And even C#: https://godbolt.org/z/5WPfT8e5G https://godbolt.org/z/5WPfT8e5G Does use the &-2 strategy. Dart also uses and: https://godbolt.org/z/1437df4En https://godbolt.org/z/1437df4En So most of languages compiled to native binaries seem to do it. Languages like Ruby and Python don't seem to optimize this, which is hardly surprising. Ruby has a JIT now, and the JIT might do it. And I'm not sure what the haskell version does, can someone explain: https://godbolt.org/z/xPP4E1a6h https://godbolt.org/z/xPP4E1a6h ?
      • tomsmeding 3y ago
        If you change the code from "n `mod` n" to "n `mod` 2", and add "-O" as a compiler flag, you'll see an "and" with 1 pop up in the assembly. Without -O, what's happening is that "mod" is a method from the Integral type class (for the non-haskellers: read "interface"/"abstract class"), and thus the program just reads the corresponding field from the stafically allocated copy of the Integral dictionary for Int, and subsequently calls it. Of course one should just inline this known function call, and that's precisely what -O lets ghc do.
        • 3y ago
• kaetemi 3y ago
  Lmao. The copyright headers.
  • gitgud 3y ago
    Didn’t notice that, incredible > Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law
• Der_Einzige 3y ago
  I was hoping that this would be about someone finally building an LLM out of a decision tree or decision tree derived technique (which ultimately boils down to nested if statements). Not sure why no one has tried it yet.
  • OscarCunningham 3y ago
    My understanding is that they are using increasingly small precision on the floats used by LLMs. So we just have to wait for them to reach 1-bit precision.
• matrix2596 3y ago
  its funny but the large language models can be seen as billions of if statements learnt from data
  • iopq 3y ago
    Not really, since they do a mathematical function over blocks and don't need a single if statement. They map learned data + input -> output as a pure function
    • ryanlbrown 3y ago
      ReLU is if-like since it only passes half of the input values with the other half becoming 0
    • LargeTomato 3y ago
      Is ML different than if statements? Yes. But is it reallllly different? No not so much.
• deleted 3y ago
  [deleted]
• Joker_vD 3y ago
  If your programming language of choice has no arrays (like most of the languages implemented in one of the many, many, many "How to write your own interpreter/simple compiler" tutorials out there) but supports variables, then you can use this technique to kinda implement them anyway, Okasaki-style: var arr0, arr1, arr2, arr3, arr4, ..., arr65535 : int; func get_arr(index: int): int { if index < 0 or index > 65535 { exit(); } if index < 32768 { if index < 16384 { if index < 8192 { ... if index < 2 { if index < 1 { return arr0; } else { return arr1; } } else { if index < 3 { return arr2; } else { return arr3; } } ... } else { ... } } else { ... } } else { ... } } proc set_arr(index: int, value: int) { if index < 0 or index > 65535 { exit(); } if index < 32768 { if index < 16384 { if index < 8192 { ... if index < 2 { if index < 1 { arr0 = value; } else { arr1 = value; } } else { if index < 3 { arr2 = value; } else { arr3 = value; } } ... } else { ... } } else { ... } } else { ... } } It even has O(log n) access time which is actually the same complexity as accessing a RAM by a pointer anyway! Just replicate this code for any array variable you need to simulate and pre-allocate enough of the memory, it's totally free with that .bss trick anyhow. So technically, languages without arrays are about as Turing-complete as those with limited-size pointers/array indices (funnily enough Brainfuck — where the pointer is invisible to the progammer — actually is Turing-complete).
  • extheat 3y ago
• cushpush 3y ago
  Fantastic use of meta-programming, and I like the benchmarking at the end, you have clarified much for the beginner and expert alike.
• adastra22 3y ago
  I enjoyed this more than I should have.
• charcircuit 3y ago
  Here is a version with 0 if statements #include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { return printf(atoi(argv[1]) & 1 ? "odd" : "even") < 0; }
  • brokensegue 3y ago
    Still branches
    • chrismorgan 3y ago
      #include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { return printf(&"even\0odd"[(atoi(argv[1]) & 1) * 5]) < 0; }
    • charcircuit 3y ago
      Not always. Popular architectures like x86_64 and ARM have instructions for conditional moves. These instructions do not cause the processor to branch.
• winwang 3y ago
  I'm surprised no one has chimed in on how the program is "processing" 40GB of instructions with only 800 MB/s * 10s of disk read. If I had to hazard a guess, there's some kind of smart caching going on at the OS level, but that would entail the benchmark of "n close to 2^32" not being run correctly. ...Or that the CPU is smart enough to jump millions of instructions ahead.
  • treffer 3y ago
    > my beefy gaming rig with a whopping 31.8 GB of memory So a rerun of the program should only need to load ~8GB if the filesystem caching is somewhat loop/scan resistant. My first thought was "probably the math is wrong", but looks like it adds up to something reasonable - especially as all numbers are rather vague / rounded (e.g. let it be 12s) and the number was just high, not absolute maximum.
    • winwang 3y ago
      I guess this would be the expected, though boring, answer -- "incorrect" benching (i.e. clear the cache first).
  • jeffreygoesto 3y ago
    It mmaps the program, unused pages then only take a page table entry and are not loaded. The only page actually loaded is the one he directly jumps into. Neat trick.
    • Liquid_Fire 3y ago
      It's not jumping directly, it's executing sequentially, comparing against each consecutive number in sequence.
      • jeffreygoesto 3y ago
        You are right, my bad. Thanks for clarifying it.
  • 3y ago
• Patient0 3y ago
  I feel like the whole article is an allegory of LLM development (as a critic would write it: devoting a stupendous amount of resources and 'training data' to 'memorize' the solution). I wonder if this was the author's intent?
  • Semaphor 3y ago
    Considering I expected it to be about LLMs from the title (I thought it would be an announcement of a new 4B model), I’m going with "probably" ;)
    • idonotknowwhy 3y ago
      Glad I'm not the only one who thought that lol
  • jgilias 3y ago
    Reading the headline I totally expected it to be about LLMs.
  • larodi 3y ago
    right so! Like the 40b LLM model doing for loops. It very much seems this allegory is the actual motivation behind the article… is not about engineering but the absurdity that awaits us around the corner.
• oefrha 3y ago
  This approach is perfect for the is-even npm package[1], with 196,023 weekly downloads, or the is-odd npm package[2], with 285,501 weekly downloads. Wouldn't it be cool if you type `npm install` and it starts downloading a 40GB is-even and a 40GB is-odd? [1] https://www.npmjs.com/package/is-even https://www.npmjs.com/package/is-even [2] https://www.npmjs.com/package/is-odd https://www.npmjs.com/package/is-odd
  • chrisandchris 3y ago
    The funniest (or best part) about those two packages is that is-even has a dependency to is-odd and does just negate the output of is-odd.
    • jl6 3y ago
      It’s true, the great thing about clean, reusable, modular code like this is that you can compose both of these packages to make a is-even-or-odd package.
      • lvncelot 3y ago
        Well first you need to obviously build an OR package, part of your suite of logical operator packages, all depending on your battle-tested, high performance XOR package.
      • wiseowise 3y ago
        Groundbreaking!
      • kparaju 3y ago
        You joke... but https://www.npmjs.com/package/is-odd-or-even https://www.npmjs.com/package/is-odd-or-even
    • layer8 3y ago
      If would be even funnier if is-odd would simultaneously do the same thing in reverse.
  • 3y ago
• raegis 3y ago
  This is one of the most entertaining articles I've ever read here. He should put the source code online so ChatGPT can "learn" from it.
  • hoherd 3y ago
    That would definitely violate his strict license: /* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/ And with such elegant code, who can blame him?
    • kparaju 3y ago
      OpenAI see. OpenAI ignore. OpenAI train.
    • prossercj 3y ago
      To what extent does the law allow persecution?
    • throwaway2037 3y ago
      LOL. "persecuted" -- I just noticed this!
• bryanlarsen 3y ago
  That reminds me of my first program ever as an 11 year old. Not only did I not know about modulus, I didn't know about less than or greater than. The program picked bingo numbers. So there were 5 lines that looked something like `10 IF n=1 OR n=2 OR n=3 OR n=4 OR n=5 OR n=6 OR n=7 OR n=8 OR n=9 OR n=10 OR n=11 OR n=12 OR n=13 OR n=14 OR n=15 THEN l="B"`
• wenyuanyu 3y ago
  better to keep "4 billion" in the title... I was confused with "4 bytes" before open the link
• faizshah 3y ago
  This metaprogramming reminds me of the post where they serialized data to ruby code to get around a slow XML parser: https://news.ycombinator.com/item?id=36311924 https://news.ycombinator.com/item?id=36311924 I’m curious if anyone has found a serious application for metaprogramming large amounts of data in a high level language like this? So far the only application I have thought of was meta programming a series of api calls before executing them so the entire transaction can be replayed as a script.
  • SCUSKU 3y ago
    Somewhat pedantic here, but would the authors use of python to generate C code be considered metaprogramming as opposed to code generation? I thought metaprogramming typically involved writing code that can alter/augment itself, like new syntax. Personally, I have found a lot of use in code generation, for example using RTKQuery's codegen tool that accepts an OpenAPI schema and outputs a JS client.
    • teo_zero 3y ago
      I would argue that code generation is a form of metaprogramming, no opposition here.
  • Retr0id 3y ago
    A while back I was reverse engineering a mobile game that used a completely custom serialization format for game data, most of it in one giant "config" blob several megabytes in size. I'd written a parser and serializer for it in Python, using custom classes to represent the various nested object types, but I didn't have a convenient way to explore and edit the data. So, I wrote some code to parse the giant blob and emit a python source file, consisting of a whole bunch of nested class constructors (with named parameters etc. making it quite readable), and a final function call to serialize the whole lot back into a blob. Now I could edit that source file and run it, and have my source-level edits reflected in the output blob (which I could subsequently feed back into the game engine to see the results of my changes).
    • 3y ago
• notfed 3y ago
  > modulus operation Isn't it normally called the modulo operation?
  • eurekin 3y ago
    Maybe it's a modulo operation squished together with the modus operandi, for laughs
• brcmthrowaway 3y ago
  The skeleton of this post can make a good interview question
• brcmthrowaway 3y ago
  Those APIs seem like fake pseudocode, until I realized... Windows
• glandium 3y ago
  It's kind of ironic that the python generator script uses modulo. The author could have pushed it to the point of not using one. I'm tempted to write a followup doing even crazier things...
  • eru 3y ago
    Author should have perhaps bootstrapped a script that doesn't use modulo?
  • deleted 3y ago
    [deleted]
  • layer8 3y ago
    Clearly the solution is to factor each number and to (recursively) test the parity of the sum of the factors. Since all prime numbers other than 2 are known to be odd, the parity test for the case of a single factor is easy. You only need to special-case 4 to avoid an infinite recursion.
  • ryanjshaw 3y ago
    I'm pretty sure that was an intentional joke. I do wish it'd have been a bitwise AND with 1.
• Retr0id 3y ago
  > for the large number close to the 2^32 limit the result is still returned in around 10 seconds. This could be improved by arranging the if/else statements in a binary tree.
  • elwell 3y ago
    This is a great idea! Intuitively, I think it might make the program 3x size though?: first `if` for ==, then an `else if` for <, then `else` for >.
    • vitiral 3y ago
      it would be extremely humorous if it actually *reduced* the speed since it required loading so much more code.
  • hansjorg 3y ago
    Come to think of it, I'm sure there are other optimisations you could do as well.
  • Scarblac 3y ago
    It could also simply check the most common numbers first. We can spider the Internet and collect all usages of numbers, sort them, and find out what the optimal order is.
    • Retr0id 3y ago
      True - given probability weights, the optimal decision order would be a Huffman tree https://en.wikipedia.org/wiki/Huffman_coding https://en.wikipedia.org/wiki/Huffman_coding
  • Scarblac 3y ago
    I don't think it would help, you'd still need the 4 billion if statements to decide whether to take the left or the right branch from the root.
    • 3y ago
• Subdivide8452 3y ago
  Can’t you just test the last digit of main’s arg and get the best of both worlds?
  • projektfu 3y ago
    "just" https://dohertyjf.medium.com/just-dont-say-just-4c3c4cde3ebb https://dohertyjf.medium.com/just-dont-say-just-4c3c4cde3ebb /s
    • Subdivide8452 3y ago
      Ironically, I have no idea what you’re implying with this reply. Should I drop the usage of the word ‘just’? Isn’t it clear what I’m saying?
• friedrich_zip 3y ago
  This is amazing technology. You should sell it to AWS so they can offer an Enterprise-ready AWS EvenOrOdd API for everyone who does not know how to host the 40GB executable properly. With the power of the cloud this programme would be unstoppable
  • MBCook 3y ago
    It’s just begging to be a Lambda function.
• BillyTheKing 3y ago
  why though? this is exactly what databases have been invented for! One could simply store a mapping of numbers to their classifications as 'even' or 'odd' in an SQLite database. This approach has the added benefit of not requiring program updates whenever a number's classification changes from odd to even.
  • Mattasher 3y ago
    Databases still have to be maintained and updated. You're better off setting up an Ethereum contract with proper economic incentives for others to act as an oracle and return the proper answer at any given time.
    • ep103 3y ago
      Anyone want to try to figure out the gas costs for deploying 30GB worth of smart contracts? xD
  • twic 3y ago
    AWS's Elastic Cloud Parity already provides this, and is far more scalable.
  • layer8 3y ago
    Yes, this seems like the kind of thing that should be in Wikidata. Then you also don't have to keep the database locally and can simply do a quick HTTPS request. (The only problem might be if TLS itself needs an even/odd function, but it probably doesn’t.)
    • peteradio 3y ago
      > The only problem might be if TLS itself needs an even/odd function, but it probably doesn’t. Doesn't sound like its ready for cloud scale.
    • mminer237 3y ago
      I like this option just because then it makes it easy for anyone to update the data when future changes arise.
• KETHERCORTEX 3y ago
  Come on, we live in 2023 and we can achieve better performance. It should be parallelized with checks evenly distributed between GPU cores. Unless you think that efforts by NVIDIA and AMD should be wasted.
• NKosmatos 3y ago
  I’m pleasantly surprised that nobody started the discussion on whether zero is odd or even ;-) https://en.wikipedia.org/wiki/Parity_of_zero https://en.wikipedia.org/wiki/Parity_of_zero
  • eru 3y ago
    I find it hard to understand how someone can be confused about that. But I dimly remember talking to people with this confusion in the past.
    • contravariant 3y ago
      It's apparently confusing enough that if you ban odd license number plates then the cops don't want to arrest anyone whose license plate ends in 0 because they're not sure if it is even or not. At least that was the case in Paris in 1977, when they alternated between odd/even license plates every day to limit the number of cars.
      • eru 3y ago
        Interesting. Do you have a source for that?
        • Snarwin 3y ago
          It looks like bans for odd/even license plates were used in Paris in 2014 [1] and 1997 [2], but not before then. However, a similar scheme was used to ration gasoline in the US during the 70s [3]. The only source I can find for the claim about police confusion is the one cited by Wikipedia [4], whose reliability I'm inclined to doubt based on the 1997/1977 discrepancy. [1] https://www.npr.org/sections/thetwo-way/2014/03/17/290849704/to-clear-its-air-paris-tests-odd-or-even-driving-days https://www.npr.org/sections/thetwo-way/2014/03/17/290849704... [2] https://www.wired.com/1997/09/paris-smog/ https://www.wired.com/1997/09/paris-smog/ [3] https://www.npr.org/sections/pictureshow/2012/11/10/164792293/gas-lines-evoke-memories-oil-crises-in-the-1970s https://www.npr.org/sections/pictureshow/2012/11/10/16479229... [4] https://en.m.wikipedia.org/wiki/Odd%E2%80%93even_rationing#Dealing_with_0 https://en.m.wikipedia.org/wiki/Odd%E2%80%93even_rationing#D...
• quickthrower2 3y ago
  Home run! (First blog post blows up on HN)
• zimpenfish 3y ago
  Weirdest bit is this, I think. > After all, IPv4 is still standing stronger than ever, 60 years after it was deemed deprecated due to so called “address exhaustion”. IPv4: deprecated in 1963, 19 years before it was introduced.
  • stanac 3y ago
    The whole article is full of jokes. > the C programming language as it’s by far the fastest language on the planet to this day (thanks to the visionary genius Dennis Richie) Which would be more or less true, but: > I decided to use the slowest language on the planet, Python (thanks to the visionary genius of Ross van der Gussom) > So I let the mighty snake do its work and after getting a cup of coffee and getting back to check on the program 48 hours later I was left with a beautiful c file
• junon 3y ago
  It took me way too long to realize this was satire. It was a stressful read up until that point.
• keepamovin 3y ago
  This was hilarious thank you. Many lols
• japanman185 3y ago
  [dead]
• gverrilla 3y ago
  First program I ever wrote was to bypass an anti-afk program in a game: it needed to click on a button which was x vs y pixels, and would appear on random positions on the screen every time. I manually inserted one line for each viable position using x-1 and y-1. In v2 I implemented a for loop which made the script go from tens of pages to not even a single full one - computer magic! (EasyUO language)
• ykonstant 3y ago
  Although not quite as spectacular as that, here is some funny codegen in POSIX shell I wrote; `sh` doesn't have a `repeat` command, so I wrote a script to implement it without forcing any loops at all. Along the way I uncovered some interesting segfaults for most sh implementations (including, sadly, dash), which is the reason for the somewhat convoluted code. Have fun! #!/bin/sh # # Usage: repeat TIMES COMMAND # Repeat COMMAND a given number of TIMES. eval_full_quotes=' s/\\/\\\\/g ; s/\"/\\\"/g ; s/</\\</g ; s/>/\\>/g ; s/\$/\\\$/g ; s/\[/\\\[/g ; s/*/\\*/g ; s/?/\\?/g ; s/|/\\|/g ; s/&/\\&/g ; s/~/\\~/g ; s/=/\\=/g ; s/;/\\;/g ; s/ /\\ /g ; s/%/\\%/g ; s/`/\\`/g ; s/(/\\(/g ; s/)/\\)/g ; s/{/\\{/g ; s/}/\\}/g ; s/#/\\#/g ; s/'"'"'/\\'"'"'/g' errorx() { printf 'Error: %s\n' "${*:-"unknown error."}" >&2; exit 1; } _rep() { rep_times="$((2 * $1))" rep_string="$2" output="" while [ 0 -lt "${rep_times}" ]; do test 1 -eq "$(((rep_times /= 2) % 2))" && output="${output}${rep_string}" rep_string="${rep_string}${rep_string}" done printf '%s' "${output}" } { times="$1" shift test 0 -lt "${times}" || errorx "First argument must be a positive integer." test 0 -lt "$#" || errorx "No command given to repeat." repeat_command="$*" command_length="${#repeat_command}" max_arg="${ARG_MAX:-"$(getconf ARG_MAX)"}" if [ "${max_arg}" -le "$((times * (command_length + 2)))" ]; then : "$(( block_size = max_arg / (20 * (command_length + 2)) ))" : "$(( blocks = times / block_size + 1 ))" : "$(( remainder = (block_size + (times % block_size)) % block_size ))" eval_string="$(_rep "${block_size}" "${repeat_command}; " | sed -e "${eval_full_quotes}")" while [ 0 -lt "$((blocks -= 1))" ]; do eval eval "${eval_string}" done eval_string="$(_rep "${remainder}" "${repeat_command}; " | sed -e "${eval_full_quotes}")" eval eval "${eval_string}" else eval_string="$(_rep "${times}" "${repeat_command}; " | sed -e "${eval_full_quotes}")" eval eval "${eval_string}" fi } exit
• timrobinson333 3y ago
  I'm afraid I take issue with the phrase "amazingly performant". I would struggle to come up with another way of determining whether a number near 2^32 is even that takes anything like 10 seconds
  • christophilus 3y ago
    I'd bet this is slower: function isEven(n) { let arr = []; let sign = -1; for (let i = 0; i < Math.abs(n); ++i) { arr = [...arr, sign]; sign *= -1; } return arr.length === 0 || arr.reduce((a, b) => a + b) === 0; } But I'm not going to test it, because I'm doing productive things on my computer right now, and don't want to OOM. Sadly, the OP missed an opportunity to call his program "blazingly fast" [0]. [0] https://www.youtube.com/results?search_query=primagen+blazingly+fast https://www.youtube.com/results?search_query=primagen+blazin...
• furyofantares 3y ago
  I wish I still had one of the earliest programs I wrote. It would have been 1996, I was 16, and I had a linear algebra book which had an appendix entry on computer graphics. I had taken a programming class the prior quarter. I got hooked writing a program to draw rotating wireframes of a few different shapes. I almost failed the class because I was so distracted by this. I didn't know about arrays yet. Every vertex was its own variable with a hardcoded default. Every entry in the rotation matrices was its own variable. The code to do matrix multiplication therefore didn't have loops, just a long list of calculations. Which had to be duplicated and adapted to every vertex. I did know about pointers, I had to draw to the screen after all, which was done by writing to memory starting at a known address. So at least I had loops rasterizing the lines between vertices. Which means I definitely had the concept of arrays and indexing into them, I just didn't know enough to make my own.
  • sbarre 3y ago
    Do you recall which shapes you created?
    • furyofantares 3y ago
      I remember there were 3, and that there was a cube and a pyramid. I can't recall the third. Maybe I did both a square pyramid and a triangular pyramid.
  • phkahler 3y ago
    Same. When I was 12ish trying to write a Pac-Man game in basic, I dreaded writing the logic for the 4 ghosts. I'd need separate code for the ghosts at (x1,y1)....(x4,y4) and said to my dad it would be cool if I could use xn and yn inside a for loop, but those are just 2 more variables. I wanted n to indicate which one. This seemed kind of weird, but it's what I really really wanted. He grabbed the little basic book and showed me that x(n) was actually a thing! I think back to this in discussions about teaching. Abstract concepts are best understood when the student has a legitimate need for them. You can explain something all day and have their eyes glaze over wondering why something is important, but if it solves a problem they have it will click in seconds or minutes.
• maxlin 3y ago
  I'd be interested in seeing how this would have gone with a switch statement instead.
  • reidrac 3y ago
    Yep, I was thinking a switch statement may be better. I mean, if we don't take into account that implementing this is just a joke anyway :D
• majke 3y ago
  In the blog post "Branch predictor: How many "if"s are too many?", I started with the same premise, but focused on branch predictor :P https://blog.cloudflare.com/branch-predictor https://blog.cloudflare.com/branch-predictor
• bilinguliar 3y ago
  It seems over-engineered to me. Why go through all the hustle of code generation? It can be solved with a simple “for loop”: func isOdd(n int) bool { var odd bool for i := 0; i < n; i++ { odd = !odd } return odd } Playground link: https://go.dev/play/p/8TIfzGrdWDF https://go.dev/play/p/8TIfzGrdWDF I did not profile this one yet. But my intuition, and my industry experience, tell me that this is fast.
  • javajosh 3y ago
    You, sir, are a raging psychopath. You have found a local maxima of brevity and absurdity and I, for one, salute you.
  • clarkdale 3y ago
    You can improve this with tail recursion.
  • YetAnotherNick 3y ago
    It will iterate infinitely for n=infinite.
    • WJW 3y ago
      Is infinite even or odd?
      • Exoristos 3y ago
        Yes.
      • YetAnotherNick 3y ago
        Ideally it should throw exception I guess.
      • KingLancelot 3y ago
        [dead]
  • gpm 3y ago
• stevefan1999 3y ago
  Why do people always got skill issue and can't learn to use proper modulo arithmetic? It seems like those "TikTok idiots" always get the limelight over this kind of silly thing
• usrbinbash 3y ago
  > Running this gives us a nice 40 GB file which contains all 4.2 billion comparisons needed to determine if any 32 bit number is even or odd! For some reason I am thinking of npm now ...
• foxhop 3y ago
  performant != high performance he used it twice so I felt compelled to state this
• vid 3y ago
  What was really hurting me was all the literal strings "even" and "odd." I would have made them into constants. I guess then the next step would be to use constants for all the numbers.
• schaefer 3y ago
  From the article: “Now, in a world where AI is replacing programmers by the minute, taking their jobs and revolutionizing the way we think about code, maybe we should…” Excuse me ?!? I get that job loss due to AI is a common fear. But is there any hard evidence that the job market is losing “a software engineering job a minute” to AI? That’s 525600 jobs annually…
  • depaulagu 3y ago
    I think this is a joke
    • schaefer 3y ago
      Gotcha. I’ll consider myself “swoooshed”.
• kolinko 3y ago
  He should've used regex for that.
  • btdmaster 3y ago
    Not as exciting as PCRE checking for primality, but: python -c 'import re;print(re.match(r"^(.*)\1$",abs(int(input("n=")))*"1")and"Even"or"Odd")'
• MPSimmons 3y ago
  This is the kind of insanity I miss from the early internet. Excellent job. Thank you for this.
• tcgv 3y ago
  > In fact, the above code is a perfect example of a time-memory tradeoff Not as much since the program will take increasingly more time to run as the input number gets higher. Checking if a 'small' number is even or odd will be pretty fast. Checking a 'large' number will be slow since it will go through all 'IFs' until it reaches the result. It's like O(M/2) average time complexity where 'M' is a constant, the program memory size (number of 'IFs' stored).
  • vitiral 3y ago
    I took it as a joke. The tradeoff is the programmer's time and memory, not the computer's
• phkahler 3y ago
  Clearly they should have optimized using binary search. Use nested if-else statements 31 deep. This would require using a more sophisticated comparison like < less than instead of equals. You'd get a similar amount of code, but it would execute on O(logN) instead of O(N). That would surely be the mark of an expert. ;-)
• HeavyStorm 3y ago
  Why did I waste my time reading this? Hahaha
• dorfsmay 3y ago
  That work is amazing! Now before you laugh at the original meme and the use of AI chosing the wrong algorithm, read this: https://fosstodon.org/@gabrielesvelto/110592904713090347 https://fosstodon.org/@gabrielesvelto/110592904713090347 There is no proof AI was used, but: > Google's code was allocating 20000 variables in a single frame.
• winddude 3y ago
  I to do lots of "researching" on social media.
• Racing0461 3y ago
  > ; add the next 2...2^32-1 comparisons here Chatgpt is getting so lazy these days.
• asylteltine 3y ago
  The TikTok is fake. Obviously it was created to drive engagement. Everything you see on TikTok is there to manipulate your emotions.
• docfort 3y ago
  So I honestly thought that this was going to be another LLM article, but using the venerable ReLU activation function instead of the usual. A ReLU is exactly an if statement when rendered in a decision tree (if less than 0, emit 0; otherwise, emit the input). Given the relative popularity of the 4B parameter models (any transformer is dominated by the number of parameters in good old fully-connected feedforward layers), you can perhaps describe such models as 4B if statements. I was disappointed that the author didn’t go there as a means of parody.
• cchance 3y ago
  Not gonna lie, i really thought he was gonna end it with... now lets try 64bit, and leave us hanging
• csours 3y ago
  My biggest hope for code GPTs is replacing dependencies.
• pbw 3y ago
  I like the engineering effort, but it's tainted by puerile comments like "visionary genius of Ross van der Gussom".
• kloch 3y ago
  This seems dangerously close to spawning a new busy beaver type inefficient resource utilization game
• ashvardanian 3y ago
  Jokes aside, lookup tables are a common technique to avoid costly operations. I was recently implementing one to avoid integer division. In my case I knew that the nominator and denominator were 8 bit unsigned integers, so I've replaced the division with 2 table lookups and 6 shifts and arithmetic operations [1]. The well known `libdivide` [2] does that for arbitrary 16, 32, and 64 bit integers, and it has precomputed magic numbers and lookup tables for all 16-bit integers in the same repo. [1]: https://github.com/ashvardanian/StringZilla/blob/9f6ca3c6d3cbc2b9fa090bedb6fbf0d04b788279/include/stringzilla/stringzilla.h#L1679 https://github.com/ashvardanian/StringZilla/blob/9f6ca3c6d3c... [2]: https://github.com/ridiculousfish/libdivide https://github.com/ridiculousfish/libdivide
• otteromkram 3y ago
  I wish people would stop putting open curly braces on new lines. Makes it harder to read, IMHO.
• kazinator 3y ago
  That looks like a program developed with TDD that has gone on too long without refactoring. The author probably has a billion individual tests that will all lose their value if it were to be simplified, since they would no longer correspond to special cases in the code.
• keitmo 3y ago
  I'd like to see a fully distributed version. All you need is 4B hosts (IPV6 FTW) named N.domain.com (where N varies from 0 to 4B-1). The driver app sends N to the first host (0.domain.com). Each host compares the incoming N with their N.domain.com name; if they match, return the host's true/false value. If they don't match, forward the request to (N+1).domain.com and return the result.
  • koromak 3y ago
    Don't give Suckerpinch any ideas
  • Someone 3y ago
    N+1 may overflow; using N-1 is more robust. Also, I think this can easily be implemented; you don’t need 4B hosts, just 4B DNS entries, and those, you can create with a single wildcard entry (https://en.wikipedia.org/wiki/Wildcard_DNS_record https://en.wikipedia.org/wiki/Wildcard_DNS_record)
• LASR 3y ago
  At 9, I tried to make a game that combined SimCity 2000 and Transport Tycoon Deluxe - my favs at the time. I used MFC(Windows) because my parents got me a big black book about it. My game was a simple train simulator with four trains. Each train moved turn by turn to its destination from its origin. Each train had to finish its move before the next train had a chance to move. I wrote it in C++ but didn't know much about managing the game's state or objects. But there was some fancy acceleration code in there. You "played" the game by modifying the hardcoded x,y coordinates in the code and admiring how the trains moved on screen. I thought real games used multi-threading to move each train at the same time. When I tried it, the game broke, probably because of UI updates from other threads. So I never quite built my game. But this project, with all its problems, got me into software development years later.
• 1vuio0pswjnm7 3y ago
  "Since I'm a great believer in performant code I decided to implement this in the C programming language as it's by far the fastest language on the planet to this day (thanks to the visionary genius Dennis Richie)." Fastest portable language. Assembler is faster.
• amai 3y ago
  Reminds me of that guy who scrolled to the end of Excel: https://youtu.be/sF8k3zl70os https://youtu.be/sF8k3zl70os
• OkGoDoIt 3y ago
  Ah, the holidays: when the most ridiculous and interesting technical work gets done. I love it.
• krick 3y ago
  The joke is completely lost on me. I don't even mean the person who did this — why not, after all. 1198 upvotes ATM is what confuses me. Lookup tables for computable values are not novel, nor are they a joke. This actually is a solutions for the time/memory tradeoff, as author well knows. The problem at hand is absurd, but quite primitive, so there was absolutely no doubt this can be done. No real measurements were performed, apart from the observations that it took about 10 seconds to chew through 40GB program on his computer. So what did we learn? That exe files cannot be more than 4GB? That a program with 2^32 ifs is about 300 GB? Why 1198 people found this interesting? Maybe I'm spoiled, but unlike "Hexing the technical interview" or some SIGBOVIK stuff, this doesn't seem crazy, just pointless.
  • corysama 3y ago
    The joke is that he actually did it. People have been joking about it for decades. But, the crazy bastard did it for real. It’s so extreme that no compiler could handle it. Not even any known assembler. So, he had to generate his own machine code binary to make it work. But, it works! Nutz!
  • segfaltnh 3y ago
    Sometimes people do things to be funny.
  • peeters 3y ago
    > Lookup tables for computable values are not novel, nor are they a joke It's been ages since I've done anything low-level, but I don't think 4 billion if-statements are compiled to a "lookup table" when optimizations are turned off. Each and every if statement would be evaluated in order to determine if it matches the input. This seems to be supported by OP's program outputting in much less time for small numbers than for large numbers--since the small numbers appear earlier in the code. A 4 billion case switch statement on the other hand, I would expect to compile to some kind of lookup table. Though when the data type is an unsigned int even then I'm not sure what the compiled code would look like without optimization.
    • MBCook 3y ago
• rezonant 3y ago
  Well this has been hilarious.
• irrational 3y ago
  > we need more if statements! Waiting for the Will Ferrel skit of this. Though this article was funny enough on its own. The Python program to generate the C code was hilarious.
• lowii 3y ago
  Seems like a poorly chosen example, since you could simply "lookup" the last bit of the integer to see if it is even or odd, which should be instant for any integer?
• i_k_k 3y ago
  When I was in college, I had to take an assembly language course. It was on MIPS: 32 registers. One assignment said, roughly: - Read ten numbers into an array. - Sort the numbers into the array. Nothing said I needed to read the array, so I read in the numbers, both to the array and registers, hardcoded a bubble sort on the registers, and wrote the result to the array. End of program. I was being cute. I got full marks with a note to stop being cute.
• sdwvit 3y ago
  This feels like a game of utilizing a PC at 100% capacity.
• 3cats-in-a-coat 3y ago
  I'd say wrap this with a good interface and we can optimize it later.
• orhano 3y ago
  Not to compete with your brilliant code on optimization, bu I have also written a swap routine that excels especially on numbers close to each other. I know sign function result can be put into a variable, but computers nowadays are so fast... Anyone feel free to use it. static void swap(ref int a, ref int b) { int c = (b - a) ; while (c != 0) { a += Math.Sign(c); b -= Math.Sign(c); c -= Math.Sign(c); } }
• JacobSeated 3y ago
  Interesting. How would this compare to making a while loop or recursive function, I wonder? And, what about switch statements? In theory it is said they should be faster, but I am not sure that's necessarily the case. Another option would be to keep a database with the numbers indexed, and then compare with performing a database query.
• Perepiska 3y ago
  The whole article looks like a misunderstanding to me. The author writes about a trade-off between memory and processor, although in his example both memory (on disk and in RAM) and processor are wasted (executing all IF instructions in turn). It is also strange that the author is trying to generate code in assembly language, which he does not know very well, because there is a DIV/IDIV instruction.
  • tills13 3y ago
    Dude it's a joke
• gigantino 3y ago
  When I was young I tried to make my own alarm clock. My masterplan was to print the time to the display (starting from 8 AM), wait a second and print the next value. All manually, obviously. I remember eventually giving up because it was getting too boring. I think I discovered about loops a year after the event. Great times :)
• Twirrim 3y ago
  I gave similar a shot in rust, using build.rs to dynamically create the file, inspired by the blog post. I'd been meaning to look at build.rs for a while. It seems to hit a pretty pathological compilation situation. Done as ifs, rust ran out of stack. Done as "match" it has been compiling for about 24 hours.
• gwern 3y ago
  I'm mildly surprised that the compiler seems to compile the code so literally so that the binary blows up like that with a linear runtime as well. I would've guessed that for such a straight-line execution on one of the simplest mathematical operations to yield a boolean, a modern highly-optimizing compiler would've done something with it. What would it take to make the compiler optimize this code meaningfully?
  • xoranth 3y ago
    Clang is able to convert the code to a jump table, though GCC can't. https://c.godbolt.org/z/Wq65j4rrM https://c.godbolt.org/z/Wq65j4rrM > What would it take to make the compiler optimize this code meaningfully? To make GCC compile the code meaningfully, it suffices to add a bunch of else statements: https://c.godbolt.org/z/z4KvxnbfG https://c.godbolt.org/z/z4KvxnbfG In fact, GCC gets very clever at -O3. (what matters is whether the compiler can turn the sequence of ifs into a switch statement, then both compilers have special logic to generate a lookup table.)
    • gwern 3y ago
      Interesting. I only know a little assembler, so I can't tell what -03 is producing there, but I know enough to see that it's doing some sort of loop bouncing between even/odd label choice. Is that now a constant-size binary (if still linear time)?
      • xoranth 3y ago
        What GCC is doing at -O3 is encoding even (resp. odd) numbers in a bitmap. 43690 = 0xAAAA = 0b1010101010101010 21845 = 0x5555 = 0b0101010101010101 Then sal rax, cl test eax, 43690 jne .L3 // .L3 mov edi, OFFSET FLAT:.LC1 // This is a pointer to the string "odd" call puts jmp .L2 is equivalent to C: if ((1 << number) & 0xAAAA) { puts("odd"); // x64 is little endian } So execution is constant time (it only needs to check against two constants), there's no loop. It should be advantageous compared to a jump table because it doesn't have to do two indirect jumps (though you now have branches that might mispredict). Edit: code formatting.
• Nevermark 3y ago
  As a kid I heard that circuits like adders were made from boolean algebra AND, OR and NOT gates. I played around on a big paper pad, and finally got a 4 bit adder implementation. But since my unit circuit was [A,B]->[S], instead of the canonical [A,B,carry-in]->[S,carry-out], I had to add a second layer of units to propagate the first carry onward. And a third layer of units in case that also generated a carry. Etc. So my circuit had gate of order N^2/2 and depth order of 2*N instead of gate and depth orders of N.
• Liebnitz 3y ago
  >Apple declined to comment for this article.