HNHacker News
TopNewBestAskShowJobs

OskarS

8,399 karma · joined September 4, 2016

submissionscomments
OskarS··on Making a 3D modeler in C in a week
The primary concern with this isn't necessarily the extra allocation and GC (though that plays a part too), it's the fact that you're chasing a pointer for every object. That's murder for the cache. MUCH faster to just have the data in-line in hot loops like this.
OskarS··on How to Use JSON Path
Yeah, it's not bad. Guido famously preferred the list comprehension style over the functional style, but when you have nested data types and the "monadic style" (ish) functions, it does really make sense. You could imagine it in Python (lets pretend lists have map and filter):

    data['store']['book'].filter(lambda x: x.price < 10).map(lambda x: x.title)
Yeah, not nearly as good. The syntax sugar of a.b instead of a['b'] and arrow functions instead of lambda really does make a pretty big difference.
OskarS··on Making a 3D modeler in C in a week
Probably confusing it with Java, where the only value types are the basic ones (unless you store each individual coord in a different array).
OskarS··on Making a 3D modeler in C in a week
You should check out MagicaCSG, which is a more sophisticated version (though still free!) of this: https://ephtracy.github.io/index.html?page=magicacsg#ss-caro...
OskarS··on Why SQLite Uses Bytecode
Not a public one, because they want to have the freedom to change how it works. But if you type in `EXPLAIN CREATE TABLE x(y);` or `EXPLAIN SELECT 3;` or whatever into `sqlite3`, you can see it. And it's reasonably straightforward to dig into the source code (SQLite is very well-written C) to hook that up yourself if you really wanted to.
OskarS··on "So that a truncated partial download doesn't end up executing half a script"
Windows and particularly macOS makes it difficult to run things that aren't code signed with trusted certificates. Same with packages in Linux package managers. That provides a large level of assurance that the thing you download is verified by a distributor that you presumably trust (otherwise why are you using their software?). Pipe to shell has no such guarantee: if a bad actor either MITMs you or gets access to their server and stuffs something bad in the script, you're out of luck.

Basically, if you believe that code signing is a good thing (and I hope we all can agree on that), curl to shell is not great security practice.

OskarS··on Multiple Displays on a Mac Sucks
Yeah, I was a little bit baffled when I saw the post. I move between two different multi-screen setups with different arrangements (at home and at work), plus using my laptop alone. I haven't done like a study or whatever if it remembers my window positions, but I've never been annoyed with how macOS handles it, it's classic Apple "just works".
OskarS··on GOTO (2000)
Yeah, this is a really interesting point, I should try this again with [[musttail]] on clang.
OskarS··on GOTO (2000)
Exactly. The only reason not to use goto here is because of a dogmatic opposition to ever using goto. In fact, this is a rare case where goto makes the flow of the program more clear rather than less clear, and alternate solutions are just worse.
OskarS··on GOTO (2000)
>> - Using a single goto and single label to exit several levels of scope.

> Better handled by putting the nested scope in a function and using `return`.

I dunno, that seems pretty silly to me. It's a perfectly valid use case of goto to jump out of deeply nested loops, and refactoring it to break out the inner loop in a function seems like pointless busy-work that ultimately makes the code harder to read, just so you can avoid a goto.

OskarS··on GOTO (2000)
I've been working my way through the latest volume of The Art of Computer Programming (Volume 4B, released last year) which is about combinatorial algorithms. One of the very first algorithms he presents Algorithm B, "Basic backtrack". It's like a generic backtracking algorithm that you could use to solve combinatorial problems (e.g. n-queens, things like that).

Every time I've seen this algorithm presented, it's used recursion, because that's a very natural way to express backtracking. But Knuth doesn't, he basically never uses recursion in his TAoCP algorithms, he expresses his algorithms in a "flow chart" style, not assuming things like stacks or subroutines (in fact, one of the exercises in the chapter is to convert Algorithm B to a recursive version, which he then quickly dismisses in the answer to the exercise as "elegant, and works find for small problems" but fundamentally not very high performance and not really clearer than the non-recursive version).

So, I set down to implement Algorithm B in a generic way and used it to solve n-queens. The way Knuth has written it, it can be straightforwardly translated using `goto`s (it has lines like "if so-and-so, go to step B4, else B3"), but being the modern, structured programmer that I am, i tried to convert it to structured programming using loops and if statements.

It was doable, but when benchmarking, my versions were always slightly slower than Knuth's original "goto" formulation, and honestly I don't think they were more readable either. You had to add a bunch of variables to keep some state around that was implicit in Knuth's version. The recursive version was definitely more readable, but Knuth was of course correct, you pay a performance penalty for that readability.

It was a real eye-opener. In the hands of a master, "goto"s really do have a place, and when well-deployed, they can sometimes simply be superior to "structured" code using loops, ifs and recursion.

OskarS··on Here's a puzzle game. I call it Reverse the List of Integers
Neat little problem! You could do SAT-solvers and stuff, but it's also obviously a graph search problem: each state is a vertex, each edge is an operation that leads to another vertex. So, obviously: Dijkstra works (or really just BFS, since the edges are unweighted), but not the fastest in the world.

The fun one to play with would be A-star, but you'd have to find a suitable heuristic. One obvious candidate is that if you have target list that is X long and a current list that is Y long, then you need at least abs(Y - X) steps to get there (since each step either adds or removes a number). That's admissable and would probably speed up the search quite a bit compared to regular BFS, but you could probably do a lot better. I'm thinking a heuristic based on the number of inversions or something.

I would suspect if you found a really good heuristic for A-star, that's about as good as you're going to get. Though maybe there's something more clever I'm not spotting.

OskarS··on What John von Neumann did at Los Alamos (2020)
Man, I did not think there were von Neumann truthers out there (seems like a particularly small hill to die on), but you live and you learn, I guess.
OskarS··on What John von Neumann did at Los Alamos (2020)
It may seem like a mixed blessing now, but without von Neumann architectures computers would not be what they are now. It's an ingenious, and non-obvious idea, that there should be no essential distinction between "program" and "data" (indeed, Turing machines are based on this idea as well).

von Neumann was enormously important in early Computer Science, his contributions cannot be understated. Indeed, Knuth credits him with the one of the most fundamental concepts in all of programming, subroutines (Turing had similar ideas in England around the same time). For more specific examples, von Neumann also came up with the concept of the PRNG, and the first practical algorithm (the "middle square" method). PRNGs are not obvious: before von Neumann, people had only tried generating random numbers using a table or primitive hardware RNGs. He was the one who came up with the idea to generate random numbers using arithmetic methods already present in computers. He also came up with the worlds first practical computer algorithm for sorting, merge sort. There's a huge number of other examples, early CS is riddled with ideas that can from von Neumann.

OskarS··on Trivial, but not trivially default constructible
Never realized concepts implied you can have multiple default constructors, that's hilarious. This is still a useful feature though. People complain a lot about C++ corner cases, but this is one you would probably never hit in real code, and `requires` clauses does a lot to clarify type requirements and provide better error messages (instead of getting a ten page template stack trace ending in some extremely cryptic type requirement for some nested class, you just get a short error message at the require site, explaining why a certain type isn't valid).
OskarS··on Overview: What are Cpp2 and cppfront? How do I get and build cppfront?
> Maybe it's not much extra workload, but ()$ requires you to pattern-match all bracketed content in a string as a possible capture, and the parser can't determine whether it's a capture or not until the $ or a matching close bracket.

You don't have to: you can also just parse the string backwards.

OskarS··on Overview: What are Cpp2 and cppfront? How do I get and build cppfront?
I think the original point was to make a typesafe printf that's still reasonably efficient without creating a bunch of small temporary strings. Like, if you printf like this:

    printf("Number %d, String %s", n, s);
but the types of n and s aren't int and char*, all hell breaks loose and you have the origin of a million CVEs. But how do you make that function signature typesafe, without the tools of modern templates? You sort of can't. One thing you can do is do string append stuff, but the syntax then is annoying:

    print("Number " + to_string(n) + ", String " + s);
This also creates a bunch of temporary strings, which is not ideal (and still relies on operator overloading, btw). In this world, using operators for this does make some sense:

    std::cout << "Number: " << n << ", String " << s;
Like, seen from this perspective, it's not the worst idea in the world, it does work nicely. The syntax really isn't too bad, IMHO (the statefulness part, though, really sucks). It also allows you to add formatting for your own types: just overload operator<<!

Clearly, properly type-safe std::format is vastly superior, but the C++ of the 90s simply didn't have the template machinery to make that part of the standard library.

OskarS··on gh-116167: Allow disabling the GIL
Really, any code? I thought they were adding fine-grained locks to the python objects themselves? Are you saying that if I share a python list between two threads and modify it on one and read it on the other, I can segfault python?
OskarS··on Meta outage
So lovely that the status page indicates that everything is fine except the WhatsApp Business API!
OskarS··on Fugitive Wirecard COO Jan Marsalek exposed as decade-long GRU spy
The book it's based on, Money Men by Dan McCrum, is also a spectacular read.
OskarS··on Rust wont save us, but its ideas will
Yeah, I had the same reaction, it was a very bad strawman: the author had explicitly set the function to be public in the Java example, and then not done so in the Rust example, and then argued that Rust is safer. But that's absurd: you deliberately made dropDatabase public in Java, which you could just as easily do in Rust by making it pub. The author just opted not to do that in order to argue that Rust is safer.

Your argument is fair that the "default" state in Rust is more restrictive, but the difference honestly is tiny. In practice, basically all Java code I've seen always explicitly states whether every function is private, public or protected, that's just how you write Java. Should it be compiler-enforced that you always do so? Maybe, but we're really splitting hairs here.

OskarS··on SI Units for Request Rate
Would you say that one watt is equal to one joule-hertz?
OskarS··on David Kahn has died
Oh wow. I got The Codebreakers as a Christmas gift when I was a teenager and devoured it. It’s still on my bookshelf, almost falling apart. A great work of history.

Rest in peace.

OskarS··on --libcurl
It's also just great documentation for a programming library. Like, if you're using libcurl and realize you need to do a range request (or whatever), or "copy as curl" from browser network tab, you can just do it on the command line and add `--libcurl` and find out exactly how to do that with the C library. It's the bee's knees.
OskarS··on Command-line Tools can be 235x Faster than your Hadoop Cluster (2014)
This is exactly the point of the article. From the conclusion:

> Hopefully this has illustrated some points about using and abusing tools like Hadoop for data processing tasks that can better be accomplished on a single machine with simple shell commands and tools.

OskarS··on Why Zig When There Is Already C++, D, and Rust?
The thing you're talking about is just not possible in a low-level, runtime-less language like Zig. Like, utimately Zig. libraries need to generate arbitrary assembly to run on your architecture (like if you want to write a driver or something), so you can't stop someone from just writing a thing that does the syscalls itself.

The kind of "capabilities" style languages you are talking about almost always have either a runtime that handles the actual syscalls, or they don't have the capability to compile directly to the assembly you need, everything has to pass through some library. Zig does not fit into either category: it has no runtime, and the whole point of the language is to be a low-level C replacement.

OskarS··on Why Zig When There Is Already C++, D, and Rust?
No, and it would be impossible to prevent as well: obviously library code can do anything it wants, including asking the kernel for memory.

But this is one of those things which just wouldn't happen in practice: custom allocators are so embedded in the Zig philosophy that I cannot imagine competent Zig programmers writing a library that did something like this. It's just not what you do in Zig.

OskarS··on Dynamic programming is not black magic
The bottom-up tabularization isn't always necessary, but it's a key technique that is not just "avoiding overhead" or whatever. Doing the top-down memoization, you don't know which subproblems you need to store at any given, but going bottom-up, you do, and you can usually be much more clever about memory usage and overhead.

The obvious example is Fibonacci numbers: the "top down" memoized version needs to store every Fibonacci number in memory, because you don't know what number the recursion is asking for. But if you do it "bottom up", you know that to calculate f(N), you only need f(N-2) and f(N-1). Therefore, you only need to store the last two numbers, reducing your memory usage from O(n) to O(1).

This principle almost always applies in DP problems: for the "edit distance" problem, the number possible values for the function is N^2 (where N is the size of the two words you need to compare, assuming they're similar sizes), so the memoized version takes O(N^2) memory. But if you do it the "bottom up" version, you realize that to calculate all values in a row, you just need the previous row of values. So it takes memory from O(N^2) to O(N).

Point being: turning the recursion "upside down" is not just a thing you do to be clever (or to avoid "function calling overhead", something like that), it has very real algorithmic benefits, usually because it takes MUCH less memory to do it like that.

OskarS··on Thinking in an array language
This is not quite the problem I was asking (i wanted to know how many numbers smaller than N this is true for, not the first N numbers it's true for), but it illustrates my point anyway: the i.1000 generates an array of all numbers [0,1000) that is then immediately discarded. In imperative and functional languages, you don't need to do that: in an imperative language it's just loop counter, and in a functional language with lazy evaluation (e.g. Haskell), it's a lazy list that doesn't ever store all 1000 numbers.

My question is: will J cleverly optimize away the i.1000 array? Is it lazily generated, like in Haskell? Or is this just one of those "we don't really care about the memory of the i.1000 array, it's usually small in practice"? Like, for high performance stuff, it seems relevant to me that you spend an extra O(n) memory for no real reason.

OskarS··on Thinking in an array language (2022)
I have a question about array languages that I've been wondering for a while: lets say you have the task "find all numbers smaller than N where predicate P is true". You know, like, "find all primes smaller than 1000", or "find all pythagorean triplets where Z is less than 1,000,000", something like that. The general pattern for doing this in an imperative language would be to have a for-loop that tests the predicate inside and then does something with the number. In a functional language, you'd use recursion or map/filter on a lazy list, something like that.

(to be clear, this is in the general case where you don't know exactly what P is. for the specific problem of finding primes smaller than N, you could obviously use sieves and stuff, but i'm more curious about the general pattern of problems like this)

Having only had limited exposure to array languages, my understanding is that in general the way to do that would be to do something like:

1. Generate an array from 1 to N

2. Test the array against the predicate, getting a new array with 0s and 1s (a mask, essentially)

3. Apply that mask to the array to get only elements where the predicate is true

Which is all fine, and I imagine that it takes a stupendously small amount of characters to do this. But my question is: what if N is large, and the predicate isn't true very often? Like, what if N is a billion or something? This is not an issue in the imperative/functional cases, because they don't have to generate the array in step 1, they can just loop/recurse/lazily generate the values (i.e. memory is O(1) for this). But it seems extraordinarily wasteful in array languages both of memory and resources to generate two different billion element arrays (the 1..N array and the mask) just to get out a handful of values.

That question is pretty specific, but this is one of my biggest questions about array languages in general. Aren't you always generating TONS of temporary arrays for no real reason, that will just pass through the calculation? Isn't that really slow? Or does the implementation somehow optimize this stuff away, maybe by using something like lazy evaluation?

← PreviousPage 10 of 34Next →