Live data from Hacker News

Challenging projects every programmer should try (2019)

austinhenley.com

171–180 of 346 posts

Re: Challenging projects every programmer should try (2019)

#171
post #107

Earlier quoted context omitted.

> Literally all of the listed projects, text editors, compilers, operating systems, and ray tracers, can exercise the exact same activities. In the linked article, these projects are all explicitly described as opportunities to learn about low-level stuff like how to efficiently store editable text. The difference with a web search engine is that nobody today can build such a thing completely from scratch, therefore…

I enjoy reading your discussion and just wanted to add that some people write a big scale software from scratch nowadays - for instance Marginalia for web search and Andreas Kling and team for operating system and web browser

I guess the first step in writing large scale software is to become Swedish!

Re: Challenging projects every programmer should try (2019)

#172
post #133

Earlier quoted context omitted.

Nowadays (and increasingly, going forward) it's possible to be a very productive programmer without knowing much low-level stuff. This may seem unfair to those who spent years wrestling assembly and then C pointers but that's just today's reality. It's not possible to be a "productive" musician on a traditional instrument (i.e. excluding iPads) without knowing how to play scales, chords, etc.

This is also the reason a computer with 4GB of RAM can't run Gmail and Spotify at the same time.

Google and Spotify are supposed to get among the best / most productive developers though

Re: Challenging projects every programmer should try (2019)

#173
post #107

Earlier quoted context omitted.

I don't understand why you think a search engine requires the use of "real engineering skills" like picking and choosing libraries and identifying which opportunities will yield fruitful optimization. Literally all of the listed projects, text editors, compilers, operating systems, and ray tracers, can exercise the exact same activities. I'm more inclined to think that your comment is really more revealing about what…

> Literally all of the listed projects, text editors, compilers, operating systems, and ray tracers, can exercise the exact same activities. In the linked article, these projects are all explicitly described as opportunities to learn about low-level stuff like how to efficiently store editable text. The difference with a web search engine is that nobody today can build such a thing completely from scratch, therefore…

Back when online learn-to-code courses like Codecadamy and Udemy were a fad, I remember that one of them (and unfortunately I don't remember which, and Google, ironically, turns up nothing) taught how to build a search engine in Python from scratch as a first project for complete beginners. I thought it had a reasonable level of complexity for this task.

You can still find search-engine-from-scratch courses on Udemy, complete with all the necessary algorithms [1].

[1]: https://www.udemy.com/course/build-a-search-engine-with-pyth...

Re: Challenging projects every programmer should try (2019)

#174

Total long shot. But does anyone have any good side projects that would center around simulating fluid dynamics? I’ve always been interested in aerodynamics and I’ve wanted to see if there is a way to learn more about it with my programming skills.

Sebastian Lague recently did a video on simulating fluids, which may be interesting. As always, he takes a "from scratch" approach to it. https://youtu.be/rSKMYc1CQHE?si=pXdsHlQSCpw8nY8m The GitHub repository also contains links to some of the research papers used to implement the simulation. https://github.com/SebLague/Fluid-Sim

I recently went this route. I didn’t want to set up or use Unity so I wrote my own 2D fluid simulator based on some of the same papers using Metal compute shaders (though I’d love to try again using webgpu). Sebastian’s video is great and the implementation is good. But this was a great (and fun) opportunity to look for ways to improve on it.

For starters, the way he’s doing the spatial lookup has poor cache performance, each neighbor lookup is another scattered read. Instead of rearranging an array of indices when doing the sort, just rearrange the particle values themselves. That way you're doing sequential reads for each grid cell you look for neighbors in, instead of a series of scattered reads. The performance improvement I got was about 2x, which was pretty impressive for such a simple change.

The sorting algorithm used isn’t the fastest, counting sort had much better performance for me and was simpler for me to conceptualize. It involves doing a prefix sum though, which is easy to do sequentially on the CPU but more of a challenge if you want to try keeping it on the GPU. "Fast Fixed-Radius Nearest Neighbors: Interactive Million-Particle Fluids", by Hoetzlein et al [0].

Or, if you want to keep using bitonic sort, you can take advantage of threadgroup memory to act as a sort of workspace during bitonic merge steps that are working on small enough chunks of memory. The threadgroup memory is located on the GPU die, so it has better read/write performance.

I ended up converting his pure SPH implementation to use PBF ("Position Based Fluids", Macklin et al, [1]), which is still SPH-based but maintains constant density using a density constraint solver instead of a pressure force. It seems to squeeze more stability out of each “iteration” (for SPH that’s breaking up a single frame into multiple substeps, but with PBF you can also run more iterations of the constraint solver). It’s also a whole lot less “bouncy”. One note: I had to multiply the position updates by a stiffness factor (about 0.1 in my case) to get stability, the paper doesn’t talk about this so maybe I’m doing something wrong.

The PBF paper talks about doing vorticity confinement. It’s implemented exactly as stated in the paper but I struggled for a bit to realize I could still do this in 2D. You just have to recognize that while the first cross product produces the signed magnitude of a vector pointing out of the screen, the second cross product will produce a 2D vector in the same plane as the screen. So there’s no funny business in 2D like I had originally thought. Though, you can skip vorticity confinement, the changes aren't very significant.

There’s a better (maybe a bit more expensive) method of doing surface tension/avoiding particle clustering. It behaves a lot more like fluids in real life do and avoids the “tendril-y” behavior he mentions in the video. "Versatile surface tension and adhesion for SPH fluids" by Akinci et al [2].

One of the comments on Sebastian's video mentions that doing density kernel corrections using Shepard interpolation should improve the fluid surface. I searched and found this method in a bunch of papers, including "Consistent Shepard Interpolation for SPH-Based Fluid Animation" by Reinhardt et al, [3] (I never implemented the full solution that paper proposes, though). There's kernel corrections, and then there's kernel gradient corrections, which I never got working. With the kernel corrections alone, the surface of the fluid seems to "bunch up" less when it moves, and it was pretty simple to implement. Otherwise, the surface looks a bit like a slinky or crinkling paper with particles being pushed out from the surface boundary.

I found [0] and [1] on my own but I found [2] through a thesis, "Real-time Interactive Simulation of Diverse Particle-Based Fluids" by Niall Tessier-Lavigne [4]. I also use the 2nd order integration step formula from that paper. It has some other excellent ideas that are worth trying.

Many years ago I used a paper (that is in fact one referenced by Sebastian’s video) and some C sample code I found to write an SPH simulator in OpenCL. I had been wanting to write one again but this time get a real understanding of the underlying mathematics now that I have some more tools under my belt. I owe it to Sebastian that I finally started on my implementation and I understand SPH a lot more now.

[0]: https://on-demand.gputechconf.com/gtc/2014/presentations/S41...

[1]: https://mmacklin.com/pbf_sig_preprint.pdf

[2]: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

[3]: https://www.hdm-stuttgart.de/hochschule/forschung/forschungs...

[4]: https://project-archive.inf.ed.ac.uk/ug4/20181074/ug4_proj.p...

Re: Challenging projects every programmer should try (2019)

#175

Earlier quoted context omitted.

You mean, the beach?

It is a joke based on needing to define "from scratch". Similar to, "how do you bake a cake from scratch? First you must create the universe." Op is gathering the raw ingredients to start fabricating his chips.

Yeah, that’s sand. :)

Re: Challenging projects every programmer should try (2019)

#176
post #133

Earlier quoted context omitted.

Nowadays (and increasingly, going forward) it's possible to be a very productive programmer without knowing much low-level stuff. This may seem unfair to those who spent years wrestling assembly and then C pointers but that's just today's reality. It's not possible to be a "productive" musician on a traditional instrument (i.e. excluding iPads) without knowing how to play scales, chords, etc.

Tell that to most guitarists. Vast majority are self taught and can’t read music; a number are excellent players.

They can't read music, but they can still make their hands move in repeatable patterns without thinking about each finger position, which I think is roughly the equivalent of implementing quicksort.

As someone who has played guitar on and off for years as a hobby, I'm shocked by how much harder it is than programming.

I can pick up almost any random codebase on GitHub, and as long as they use libraries and don't touch low level stuff, I can probably start working with it in 10 minutes to a day at most.

Then, I could leave that project for a year and be almost as productive as when I left. So much of the action is on the screen, not in the head, and there's no muscle memory required.

If any instrument was as easy as coding... I think a lot of coders might have music careers instead....

Re: Challenging projects every programmer should try (2019)

#178
post #24

While writing a text editor, a compiler, an operating system, or a raytracer might make you a better programmer, it won't make you a better software engineer. In fact, it might make you worse at software engineering, because it embodies the disastrous "Not Invented Here" doctrine. Hackers like to obsess about Big-O, data structures, HoTT, and other high-theory stuff, yet the following skills, essential for software e…

This sounds like sensible advice. But there are a few problems with making software purely from ready-made building blocks. Here are two of them: 1) Much more often than not, the ready-made building blocks are crap. Your software will reflect that crappiness, and your life will consist not of writing software, but of maintaining and massaging crap. 2) Even if your ready-made building blocks are high-quality, they lim…

> But I have bad news for you. This kind of software will soon be written not by you, but by an AI

Press X to doubt

Re: Challenging projects every programmer should try (2019)

#179
post #107

Earlier quoted context omitted.

I don't understand why you think a search engine requires the use of "real engineering skills" like picking and choosing libraries and identifying which opportunities will yield fruitful optimization. Literally all of the listed projects, text editors, compilers, operating systems, and ray tracers, can exercise the exact same activities. I'm more inclined to think that your comment is really more revealing about what…

> Literally all of the listed projects, text editors, compilers, operating systems, and ray tracers, can exercise the exact same activities. In the linked article, these projects are all explicitly described as opportunities to learn about low-level stuff like how to efficiently store editable text. The difference with a web search engine is that nobody today can build such a thing completely from scratch, therefore…

>elitism and ego

You know those car guys who will rebuild their engine, just because? Or those retro computer guys that will recap an ancient board rather than buying a modern pc?

For you it is a job, for me it is a hobby. I have no interest in making something 'professional' I want to take it apart to understand how it works. Want to understand how a text editor works? Write one.

What component of that is ego?

It seems to me you're the elitist, you're not far off saying mere users shouldn't be allowed to modify their own software, shouldn't be allowed to install software that hasn't been okayed by the people who know what they're doing.

Re: Challenging projects every programmer should try (2019)

#180

Earlier quoted context omitted.

I don't understand why you believe low-level "intrusive" programming and general software engineering are mutually exclusive. There is a big, open field for high quality, low-level software to be written well bearing good practices and practical decisions. 1. To be faif, these kinds of "hacking" projects aren't technically meant for learning software engineering in the context of a job, but they are really interestin…

>I don't understand why you believe low-level "intrusive" programming and general software engineering are mutually exclusive. Hmm, while I don't fully agree with his comment, then your comment reminded me how I hate to discuss programming languages and programming ecosystems with C people. It feels like C/low lvl people often refer to some "standard" that they treat as a bible of programming languages even when nobo…

Honestly, that is fair. My perspective on this is as a high-level developer, looking into how the things I am using daily actually work. I haven't actually interacted with any proper low-level developer, kind of hard to come across them where I am tbh, so I don't have any clue about how snobbish they can be, but I have seen a fair share of high level devs do it too, as you mentioned. I kind of get it? It's like a way to get validation on the technology you are stuck with for the rest of your working lives, I'm guilty of pushing Flutter onto people despite having had a painful experience with it (state management is a nightmare).

But hey ultimately I just think people should satisfy their curiosities. My work is often always in Python, JS or Java, but at some point I got tired of just doing regular software development stuff and lately I've happened to gain interest in low level development. (Like any definitely sane person I chose to start with rust and decided my first ever rust project should be an emulator, so maybe I'm just dead inside and I don't know it yet)

Post reply on HN