DHowett · 2 years 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 (:

slabity · 2 years 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?

rocqua · 2 years 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.

tarruda · 2 years 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!

diegocg · 2 years ago

Compilers will actually do these kind of tricks, I have seen them doing that for switch statements with a large number of cases.

zeroCalories · 2 years ago

Why search? We know exactly where every number is. Use a jump table.

While this example is obviously silly because loading a number into a register and performimg some operations on it is going to be faster than a cache miss from jumping into a massive table, the general technique can absolutely be applied in the real world.

twic · 2 years ago

No, a binary search will defeat prefetching. A linear scan is cache-friendly and will be much faster up to a certain point. It's called mechanical sympathy, look it up.

punnerud · 2 years 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

divbzero · 2 years ago

I ran a web search to figure out if “Ross van der Gussom” was some sort of inside joke. The top two search results were OP and the parent comment.

ninepoints · 2 years ago

I would think that the title alone should indicate that this entire bit is satire.

leosanchez · 2 years ago

> This is a joke right?

I hope so. If not, it is a load of bullshit.

coldtea · 2 years 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.

speedgoose · 2 years 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 · 2 years 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.

Cyph0n · 2 years ago

I’d assume any decent compiler would optimize a “% 2” (or any power of 2) into a bitwise op. Could be wrong though!

gitgud · 2 years 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

OscarCunningham · 2 years 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.

iopq · 2 years 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

anvuong · 2 years ago

That's because array, or even if/else statements are already higher-level abstraction. To be Turing complete you simply need: a memory that can be read from or written to, and the ability to "jump" or "move" to some memory location.

Turing complete may sound big, but almost anything that can compute is Turing complete.

extheat · 2 years ago

Why would normal memory access be O(log n)? Seems to me jumping to a random address should be an O(1) operation. Would be pretty dumb if jumping to higher RAM addresses takes longer than jumping to lower RAM, excluding hardware things like different RAM sticks or page files.

brokensegue · 2 years ago

Still branches

treffer · 2 years 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.

jeffreygoesto · 2 years 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.

drewtato · 2 years ago

My guess is either compression or stuff lingering in RAM. The CPU can't be smart here since it doesn't know what any of the future ifs will be. It doesn't know they're in order, or unique, or even valid instructions. You could (theoretically; the OS probably wouldn't let you) replace an if with an infinite loop while the program is running.

toxik · 2 years ago

It can't be the CPU since it is actually memory-mapped code, and the branch predictor surely cannot cause page faults and so cannot page in the next page of code.

Truly curious. I guess the linear access pattern helps but 800 MiB/s?

rzzzt · 2 years ago

There's also anticipatory paging, the OS can guess which pages will be requested the next time around.

bob1029 · 2 years ago

I assume modern branch predictors are capable of picking up a trivial pattern like this.

hoherd · 2 years 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*/

Semaphor · 2 years 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" ;)

jgilias · 2 years ago

Reading the headline I totally expected it to be about LLMs.

larodi · 2 years 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.

chrisandchris · 2 years 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.

chrismorgan · 2 years ago

Actually it’s not good enough there because JavaScript numbers are f64 rather than u32. Even if you only support the safe integer range (beyond which the answers become somewhat meaningless), that’s 2⁵⁴, more than four million times as large as 2³². Not sure how big the machine code would be, but I’m guessing it’ll just add 4 bytes (40%) to each case, so you’re up to something like 224 exibytes. And that’s when you’re being lazy and skipping the last ten bits’ worth. If you want to do it properly, multiply by another thousand. Or maybe a little less, I haven’t thought too deeply about NaN patterns. Or maybe just infinite if it supports bigints.

lvncelot · 2 years ago

It's always worth mentioning that those packages stem from the effort of one dedicated npm spammer[1] to weasel his way into as many node_modules directories as possible. There's also packages for ansi-colors (no, not one package for all colors, one package for each color) and god knows what else. These then get jammed into any cli tool or other half-way sensible looking package, all referencing each other obviously - and any "real" project is just a single innocuous dependency away from having dozens of jonschlinkert packages.

[1] https://www.npmjs.com/~jonschlinkert

cyco130 · 2 years ago

But of course WebAssembly is the future. So we should reimplement it in WASM.

christophilus · 2 years ago

Every time I see these packages mentioned, I’m reminded of an interview with Joe Armstrong. In it, he said, (paraphrasing from memory) “Wouldn’t it be interesting if a language had a global, flat registry of functions that anyone could pull from and contribute to? That way, bugs are fixed in one place, there’s less reinvention of the wheel, things get more correct over time, and programs just become a simple composition of standard functions.”

I may be misremembering his meaning, but I remember thinking it was an interesting idea. It wasn’t obviously a terrible idea. I thought it would be like the Clojure standard library on steroids, especially if it was coordinated and vetted by a decent team.

But alas, NPM has proven it otherwise.

mickael-kerjean · 2 years ago

I did a nullll package [1] whose only purpose is to export a null and takes 400MB in memory but somehow it got flagged in HN [2]. With 41 stars on github and 100% test coverage [3], it was clearly production ready.

[1]: https://github.com/mickael-kerjean/nulll

[2]: https://news.ycombinator.com/item?id=17072675

[3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js

divbzero · 2 years ago

Amazingly, following “don’t repeat yourself” in its purest form, is-even depends on is-odd:

  /*!
   * is-even <https://github.com/jonschlinkert/is-even>
   *
   * Copyright (c) 2015, 2017, Jon Schlinkert.
   * Released under the MIT License.
   */

  'use strict';
  
  var isOdd = require('is-odd');
  
  module.exports = function isEven(i) {
    return !isOdd(i);
  };

jrpelkonen · 2 years ago

Implementing the comparisons by hand seems difficult and primitive. May I suggest introducing some helpful sub-packages and building the solution on top of those. For instance, is-odd would be implemented by using is-one, is-three, is-five, is-seven, etc.

avinassh · 2 years ago

I did something similar six years ago called gg-flip for npm - https://github.com/avinassh/gg-flip

It was submitted in HN too - https://news.ycombinator.com/item?id=16194932

jgalt212 · 2 years ago

I'd fire someone who imported those packages.

atleta · 2 years ago

I haven't heard about him but checking the source tree of our 2 front-end apps and his 'is-number' package (which his is-odd depends on), seems to be imported by quite a few other packages.

Now looking at the source, that package may make sense if figuring out whether something is a number type in JS is really that cumbersome. (Though I'd expect that there is a more generic package that covers the other built-in types as well.)

Also since isNumber treats strings that can be converted to a number, a number, it can yield weird results since adding two strings will naturally just concatenate them. So e.g.:

    const a = '1'; 
    isNumber(a); // returns true
    const b = a + a; // Now you have a string in b: '11'

geodel · 2 years ago

Big fan of code reuse. Small packages providing single unique functionality is the way to program modern systems. It has to be right if bright minds in NPM / Rust community follow this approach.

ape4 · 2 years ago

I was wondering what the code looked like...

    'use strict';
    
    const isNumber = require('is-number');
    
    module.exports = function isOdd(value) {
      const n = Math.abs(value);
      if (!isNumber(n)) {
        throw new TypeError('expected a number');
      }
      if (!Number.isInteger(n)) {
        throw new Error('expected an integer');
      }
      if (!Number.isSafeInteger(n)) {
        throw new Error('value exceeds maximum safe integer');
      }
      return (n % 2) === 1;
    };

jkrubin · 2 years ago

Theoretically only one 40gb file would be needed. AFAICT almost every odd number is not even (I cannot say "all" bc I have not checked every integer yet).

dfee · 2 years ago

The implementation of is-even is mind blowing (numbing?).

    'use strict';
    
    var isOdd = require('is-odd');
    
    module.exports = function isEven(i) {
      return !isOdd(i);
    };

xorvoid · 2 years ago

Even better if it built-on-install by executing another script to generate everything (naturally using %) New nerd game: enshitification inverse golf.

akoboldfrying · 2 years ago

Interesting that there are so many more weekly downloads for is-odd. This seems to suggest that there are many more odd numbers than even.

(Alternatively, perhaps odd numbers are actually much rarer, leading to them having a higher market value, and thus more interest in discovering them.)

SCUSKU · 2 years 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.

Retr0id · 2 years 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).

rented_mule · 2 years ago

I don't know if I'd go as far as calling it serious, but...

I have a string of 150 individually addressable RGB LEDs on a fake tree in my living room. It's controlled by an ESP32 (running ESPHome). I started generating little animations for different times of year (in the form of ESPHome light effects). I ran into a few problems:

- The edit/compile/flash/debug cycle was painfully slow.

- Expressing the animations in C++ sapped inspiration.

- Some parts of the animations are more computationally intensive than others, so getting consistent "frame rates" was difficult.

That "frame rates" bit made me realize these are just little videos with 150x1 pixel resolution. Now I write the animations in Python on my laptop and that code has two backends. One renders to the screen for quick iteration on the animations. The other plays one cycle through the loop of each animation and emits the results as C++ arrays and some variables (e.g., name, desired frame rate, etc.). Then the only other C++ code needed is the logic for passing the array data to the LED library.

There is no compression or anything else fancy. I can fit about a dozen animations with 100 to 200 frames each on a $4 microcontroller with Wi-Fi. They start almost instantly when applying power, and they play at a very consistent frame rate. The highest I have tried is 60 fps and that is no problem.

Someone · 2 years ago

https://en.wikipedia.org/wiki/X_BitMap and https://en.wikipedia.org/wiki/X_PixMap come to mind, but they usually were written by an image editor, not by a program specifically written by the programmer who needed such code in their program.

vitiral · 2 years ago

Protocall buffers are effectively code generation and are central to Google's tech stack. Does that count?

eurekin · 2 years ago

Maybe it's a modulo operation squished together with the modus operandi, for laughs

eru · 2 years ago

Author should have perhaps bootstrapped a script that doesn't use modulo?

layer8 · 2 years 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 · 2 years ago

I'm pretty sure that was an intentional joke. I do wish it'd have been a bitwise AND with 1.

elwell · 2 years 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 >.

hansjorg · 2 years ago

Come to think of it, I'm sure there are other optimisations you could do as well.

Scarblac · 2 years 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.

Scarblac · 2 years 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.

projektfu · 2 years ago

"just"

https://dohertyjf.medium.com/just-dont-say-just-4c3c4cde3ebb

/s

MBCook · 2 years ago

It’s just begging to be a Lambda function.

Mattasher · 2 years 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.

twic · 2 years ago

AWS's Elastic Cloud Parity already provides this, and is far more scalable.

layer8 · 2 years 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.)

whoopdedo · 2 years ago

    CREATE TABLE even_or_odd (
      is_odd NUMBER(1);
      is_even NUMBER(1);
      is_zero NUMBER(1);
      is_one NUMBER(1);
      is_two NUMBER(1);
      is_three NUMBER(1);
      -- ...
    );
    INSERT INTO even_or_odd (is_odd,is_one) VALUES (1,1);
    INSERT INTO even_or_odd (is_even,is_two) VALUES (1,1);

huhtenberg · 2 years ago

Correct, but you'd certainly want to use an XML database.

Not only it helps with portability of the data, it also keeps it in a human-friendly format should the need to inspect it by hand arise.

eru · 2 years 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.

raverbashing · 2 years ago

This is the kind of discussion that matters only for the very theoretical edge cases or for the pop-math inconsequential discussions

0 is even

I mean, it is the first phrase on the linked fine article:

> In mathematics, zero is an even number.

Viliam1234 · 2 years ago

Is that article about the IEEE 754 positive zero, or negative zero, or both?

vitiral · 2 years ago

I particularly liked this bit

> Not only is 0 divisible by 2, it is divisible by every power of 2, which is relevant to the binary numeral system used by computers. In this sense, 0 is the "most even" number of all.

in the arena of even one-up-man-ship, zero wins.

codeflo · 2 years ago

I always found it funny that this is printed as a reminder text on Magic the Gathering cards that care about even or odd values: https://scryfall.com/card/iko/88/extinction-event?utm_source...

But thinking about it, I have no doubt that Wizards found out this confusion is somewhat widespread during playtesting, and printing a short reminder was an easy fix.

Klaus23 · 2 years ago

I asked a few LLMs whether zero is an even or odd number to see how they fared on such a widely misunderstood question:

LLAMA 2 7B: 3x even, 2x neither

LLAMA 2 13B: 1x even, 4x neither

LLAMA 2 70B: 1x even, 4x neither

GPT 3.5: 20x even despite trying to trick it

Mistral 7B: 1x even, 3x neither, 1x even+neither?!

Mixtral 8x7B: 8x even, 2x neither

stanac · 2 years 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

christophilus · 2 years 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;
    }

Sadly, the OP missed an opportunity to call his program "blazingly fast" [0].

[0] https://www.youtube.com/results?search_query=primagen+blazin...

sbarre · 2 years ago

Do you recall which shapes you created?

phkahler · 2 years 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.

Y_Y · 2 years ago

The obvious solution here is to use the lower part of the screen as working memory while drawing the upper part. By the time you get to the bottom you shouldn't have many calculations left anyway. This has the benefit of using fast gpu ram and is therefore cuda and very ai.

almostnormal · 2 years ago

The first part of GWBasic I learned by asking someone for help was "chain", after having taught myself print, input, if, and goto from the documentation.

canjobear · 2 years ago

I did something similar for my big middle school hit, a TI-83 version of Snake. Every x and y position of every segment of the snake went into a separate variable. The snake could only get so long because TI-83 BASIC only gives you so many variables.

ljm · 2 years ago

It reminds me of one of my earliest ventures into freelancing, where all I had was a tiny VPS that supported PHP. I had to process a large spreadsheet which had maybe 5/10k entries in it. Small potatoes these days, compared to that time in 2002/2003.

I wasn't a computer scientist so I read the file in the dumbest way possible, but kept getting errors about memory usage and running out of space since I was looping within loops within loops. I went through it and added `$variable = null` at every opportunity. Lo and behold it worked.

_the_inflator · 2 years ago

Welcome to the world of optimization the hacky way on an old computer, where code is data is code, and the only truth is: does it render in as many frames as possible? ;)

Usually, you cannot achieve this by engaging in academic code with recursion and loops; you have to do the opposite: trade readability and compact code for speed.

Sometimes, code for 6510/68000 is so optimized - usually unrolled - that you get code patterns that resemble data applied at different frames, much like your code.

There is nothing wrong from my point of view. ;)

(Some words of wisdom: May the debug gods be with you on this journey, though.)

reidrac · 2 years 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

javajosh · 2 years ago

You, sir, are a raging psychopath. You have found a local maxima of brevity and absurdity and I, for one, salute you.

clarkdale · 2 years ago

You can improve this with tail recursion.

YetAnotherNick · 2 years ago

It will iterate infinitely for n=infinite.

gpm · 2 years ago

I can confirm that the rust version of this one is fast:

    playground::isOdd:
     testq %rdi, %rdi
     setg %al
     andb %dil, %al
     retq

Unfortunately the go playground doesn't seem to support emitting assembly?

flakes · 2 years ago

A true production quality implementation should always use recursion.

  func isOdd(n int) bool {
    switch {
    case n == 0:
      return false
    case n > 0:
      return !isOdd(n-1)
    default:
      return !isOdd(n+1)
    }
  }

scaredginger · 2 years ago

I think this counts as a bottom-up DP solution

devjam · 2 years ago

Don't forget the companion isEven function:

    func isEven(n int64) bool {
        return !isOdd(n)
    }

virgoerns · 2 years ago

Does Go default-initialize booleans by any chance? In C, which author had used, this program would be undefined behavior due to reading non-static, uninitialized bool.

depaulagu · 2 years ago

I think this is a joke

btdmaster · 2 years 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")'

vitiral · 2 years ago

I took it as a joke. The tradeoff is the programmer's time and memory, not the computer's

koromak · 2 years ago

Don't give Suckerpinch any ideas

Someone · 2 years 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)

corysama · 2 years 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 · 2 years ago

Sometimes people do things to be funny.

peeters · 2 years 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.

Affric · 2 years ago

My understanding was that it was a parody of these blog posts satirising the pointlessness of pushback against conventional wisdom. Rather dry.

tills13 · 2 years ago

Dude it's a joke

xoranth · 2 years ago

Clang is able to convert the code to a jump table, though GCC can't.

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

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.)