HNHacker News
TopNewBestAskShowJobs

sebastianmestre

152 karma · joined November 8, 2023

Quant Developer at GTS, teacher at UNR, former competitive programmer (3x IOI, 2x ICPC World Finals), competitive programming coach (1x IOI, 1x ICPC WF).

I like algorithms and abstraction

submissionscomments
sebastianmestre··on Language models are injective and hence invertible
I think that the latent space that GPT-2 uses has 768 dimensions (i.e. embedding vectors have that many components).
sebastianmestre··on Programming Deflation
> Jevons’. Jevons’ paradox predicts that when something becomes cheaper, demand increases as the cheaper good is economically viable in a wider variety of cases.

That's just the usual behavior of any market. When prices go down, demand goes up.

Jevon's paradox specifically says when prices go down by a factor of x, demand goes up by a factor greater than x, leading to total consumption (measured in money spent) goes up.

In the context of this post we can paraphrase (replacing money with programmers) like so:

Once AI makes it so developing any piece of software takes half as many programmers, the amount of software developed will go up by more than two times, leading to a net increase in the number of programmers required.

sebastianmestre··on Can we test it? Yes, was can [video]
They're fake internet points, it's no big deal
sebastianmestre··on Show HN: High End Color Quantizer
Very cool!

Something that always bugged me about palette generators I've used is how they end up not picking any colors intense enough for the deepest highlights/shadows, because they use colors close to the average of various sets of pixels.

The result is that the most eye-catching parts of an image end up washed out, reducing the appeal.

My hack to address this has always been making a larger image with big white/black bars around the original image to push the palette generator to include a few really bright or dark colors.

From the look of your examples, your project addresses this too, right?

Btw, I opened an issue about the graphs in your readme because, as a programmer, they don't tell me if your program is fast or not. From a user's perspective that thinks in terms of the side length of an image, the numbers presented are very useful, but they might be even more useful in table format.

sebastianmestre··on Mipmap selection in too much detail
A while back I read a paper about downsampling normal maps and converting lost detail into roughness

I can try to find it if you want

sebastianmestre··on Mipmap selection in too much detail
Fyi; you can scroll the code blocks if you zoom out until there is no more horizontal scroll on the page

Still sucky but at leas you can read the code

sebastianmestre··on You Wouldn't Download a Hacker News
Can you remake the stacked graphs with the variable of interest at the bottom? Its hard to see the percentage of Rust when it's all the way at the top with a lot of noise on the lower layers

Edit: or make a non-stacked version?

sebastianmestre··on Use Long Options in Scripts
You have a nice ternary counter going in the version numbers :)
sebastianmestre··on Show HN: FlakeUI
Runs slow as hell on my phone. Around 10fps.

My phone is not great but drawing some circles and some text should not take 100ms. On any device.

sebastianmestre··on Unintuitive optimization for performing paths union
Please tell me that, after noticing that the best interval length is 2, you simplified your implementation to something like this

    def perform_union_dnc(paths):
        if len(paths) == 0:
            return None
        if len(paths) == 1:
            return paths[0]
        middle = len(paths) // 2
        left = perform_union_dnc(paths[:middle])
        right = perform_union_dnc(paths[middle:])
        return perform_union_naive([left, right])
It's not exactly the same algorithm (top-down merging instead of bottom-up) but the performance should be very close.

Also, it can be optimized to avoid temporary lists if that turns out to be a win.

sebastianmestre··on Earth's subsurface may hold up to 5.6 × 10⁶ million metric tons of hydrogen
The figure in the title expressed in normal units

5.6 * 10^15 kilograms

sebastianmestre··on 56bits – online retro games store
I came across this store the other day while browsing LinkedIn. It's actually by the same guy who made the EspoTek Labrador electronics board (disclaimer: I contributed to the Labrador repo back in 2019)
sebastianmestre··on Can a Rubik's Cube be brute-forced?
Yeah I got that, but it's really not as interesting as it seems. Let me explain why.

Say we have an array p[1], p[2], ..., p[n] with all possible rubiks cube configurations

Then this function will solve the cube:

    move(1) = p[1]^(-1)
    move(i) = p[i]^(-1) * p[i-1]
In laymans terms, the resulting algorithm is: assume the initial configuration is p[1], then solve it. If it wasn't, undo those moves then solve as if the initial position was p[2], etc...

So, yeah. Those fixed solving sequences / hamiltonian paths are actually very common. We can make one for any permutation of the group elements.

So I posed a more interesting question: what is the simplest sequence of moves that has this property?

sebastianmestre··on Can a Rubik's Cube be brute-forced?
Yes, you can solve a cube by this simple algorithm

    i = 0
    while not solved
        apply move(i)
Interestingly, there is no constant function `move(i) = x` that makes this algorithm correct.

If there was, there would be a single element x of the rubik's cube group that generates the entire group (every element could be written as x^n)

This would imply that the group is commutative (x^n * x^m = x^(n+m) = x^(m+n) = x^m * x^n), which every cuber knows is false from experience (permuting moves does not lead to the same final configuration)

An interesting question would then be: whats the simplest piecewise-constant function that makes this algorithm work?

I.e. is it possible to use move x1 for the first n1 steps, then x2 for the second n2, then x3 for the next n3, ..., then xk for the next nk? And if so, what is the smallest k that makes it so?

sebastianmestre··on Self-referential variable initialization in C
This is also useful initializing empty circular linked lists

  node n = {
    .data = NULL,
    .prev = &n,
    .next = &n,
  };
sebastianmestre··on If the rectangle measures 6 inches by 12 inches what's the radius of the circle?
Is there a more direct or elegant solution than reducing it to a quadratic equation?

By the way r=6 is also a solution, if we treat the diagram a bit more abstractly.

sebastianmestre··on Flame Graphs: Making the opaque obvious (2017)
Width in a flame graph is directly proportional to runtime. Optimizing a block that covers x% of the graph will only speed up the program by x% or less, so probably dont bother with blocks less than 0.5% wide.

This by itself should already tell you what NOT to optimize.

But really, you should be looking for operations that take a long time but shouldn't (wide blocks that should be thin). To find it you need to have an intuitive idea of how fast things should be beforehand.

If you have no idea how fast things should be, no amount of graphs will help you with this.

sebastianmestre··on Wc2: Investigates optimizing 'wc', the Unix word count program
Yeah, Sean Barrett has a good writeup about them and optimizing them for branch-prediction, etc

It's framed in the context of programming-language tokenization, but the principles are the same.

https://nothings.org/computer/lexing.html

sebastianmestre··on Wc2: Investigates optimizing 'wc', the Unix word count program
They meant that different characters don't change the performance, unlike the Linux and MacOS versions, where different characters go through different code paths.

But yes, a bigger file does take longer to process.

sebastianmestre··on Writing a Compiler is Surprisingly Easy (part 1)
Register allocation is not on the roadmap, I think it's too hard for this series... But maybe I just haven't figured out an easy enough way to do it yet :^)

Memory allocation? You mean making a heap allocator? In the spirit of lowering the bar for creating new languages, I lean more towards calling into libc's malloc instead of building a custom solution haha

sebastianmestre··on Implementing Mario's Stack Blur 15 times in C++ (with tests and benchmarks)
In my experience, 3 passes of box blur looks good enough for small kernels (less than 50px). Is this faster than that?
sebastianmestre··on Writing a Compiler is Surprisingly Easy (part 1)
Parsing and symbol resolution on simple languages is kinda trivial in my opinion, but I'll probably write some articles about that stuff later

Control flow and pointers are coming in the next part, and it's still surprisingly easy

sebastianmestre··on Writing a Compiler is Surprisingly Easy (part 1)
That's right!
sebastianmestre··on Writing a Compiler is Surprisingly Easy (part 1)
The article describes AST -> Assembly transformation, no?
sebastianmestre··on Writing a Compiler is Surprisingly Easy (part 1)
Author here. I wanted to get the bar for writing a compiler as low as possible, and emitting assembly code seemed better in that regard.

Also I don't have time to learn x86 instruction encoding right now :(

sebastianmestre··on Writing a Compiler is Surprisingly Easy (part 1)
> There are push and pop instructions which are perfectly suited to this nested value use. In the past, lamenting how many compilers don't seem to realise that (and the fact that push/pop are specially optimised on x86 via hardware known as the stack engine)

That's fair, but in the article I also store local variables relative to %rsp, so I wouldn't want it changing at all

I could use %rbp for that instead, but then I'd have to explain it in the article :^)

sebastianmestre··on Writing a Compiler is Surprisingly Easy (part 1)
Wow! My blog made the HN front page!

I've been lurking for a while but only now made an account :^)

← PreviousPage 2 of 2