Hacker News Reader

This is in a nutshell the moral of the performance story. I took a graduate level class in performance computing that was basically all lab based. In the end what I learned, overwhelmingly, first hand, is that in the performance computing world, what wins is what exploits the hardware intelligently.

Theoretical advancements matter too but usually only in so much as they can translate to hardware. Although, there are some special case where even a slight theoretical gain matters even more than how it translates to hardware, but they're limited.

Anyways, to that end, everything becomes about dividing work in a way that parallelizes nicely, exploits cache well, reduces the need to share information between threads, etc... and this ultimately comes down to data structures. However, these aren't your normal, fundamental data structures. Instead each problem sort of has some kind of exotic, hypothetically ideal data structure, that is fine tuned to exploit the machine's resources to the max for just that problem. By the time you're done they rarely resemble anything intelligible, let alone wha the whiteboard version of the algorithm was.

In that vein, there are a few general trends that appear over and over again. Trees vs graphs is definitely one of of those trends, although that's more of a general theme and not a literal rule.

That sounds very interesting. Would you be able to reference any such exotic data structure and maybe the process of getting to defining it?

I don't know any of their names, or if they even have names. My TA for that class had, at the time, one of the world's fastest SSSP implementations, and our last class was basically just spending the whole lab time understanding his personal implementation. It was really in that moment that it clicked for me that the more you come to understanding a problem in CS the more your code morphs from something general into becoming one big, bespoke data structure. Almost his entire program was just one giant data structure. So, I don't think this kind of thing has a name, nor can I say I really even understood it, but I do remember he used a lot of bags.

For reference, we spent the whole class doing SSSP on a graph representing every road in the United States. The naive A*/Dijkstra implementation took like 45 min, and naive bellman-ford never finished (probably days/weeks). By the end of the class I was so proud to have parallelized Bellman-Ford to the point where it took like 30s or something. And my TA's record breaking implementation was <1s. All of this was on a normal university linux desktop.

It's kind of like programming = logic + data. However, there's a continuum between the two, and on the far, extreme end of that spectrum, the structured access of the data can be the program itself.

These stories really expose how fast and efficient computers can actually be. I remember a post (don’t have the link) where someone sped up a Python script by 3000x or something crazy like that with C++. A script anyone would’ve been fine running, but it was just so much slower than what was possible.

Sometimes I wonder whether we should not focus more on these micro adjustments. We usually have this “it’s fast enough” attitude, but probably everything we use today (including web services) could be instant if focus was given to optimization (although yes, I understand the drawbacks of focusing solely on that).

We as in the general every day programmer especially your web services example should definitely not focus on these micro adjustments I would say. Sure it's fun. If you make library type code, yes please do focus on them! If you're a run of the mill corporate dev, very rarely I would think.

Other much simpler optimizations are usually possible in "corporate code". Lots of stupid things being done. To use your python script example, proba ly you could've gotten 2950x improvement rewriting the bad parts better but still in python :)

Do you remember what the python script did/was for? How much time was spent building the original script? What was the guy that built it paid?

How long did it take to build the C++ version and how much was that guy paid?

If these were all open source/unpaid, what would it cost for these different types of people and could the company conceivably pay those salaries/keep the guy happy and busy enough to stay around?

I understand all that and apply that day to day. But my thought here is more to think of the possibilities if the performance of most things was brought to its absolute best. There’s a company that went from 30 servers to 2 just by rewriting from Ruby to Go (I can find the link later if interested). Even if they had kept Ruby and achieved a speed up, there was something just massively inefficient and they didn’t really care as they were in “we're shipping fast” mode and were making money. Which I understand perfectly but that’s a big waste of energy and resources.

Not that I think that should be priority #1 but it’s staggering how much more efficient things can be than the “naive” approach.

Perhaps you're thinking of Matt Parker's (of standup maths and numberphile fame) video:

https://m.youtube.com/watch?v=c33AZBnRHks

I think that’s it! Really shows my point: the first code was already ok and solved the problem in a reasonable amount of time, in a normal “let’s ship faster” setup the ridiculous speed up achievable would’ve never even be considered. 4 million percent faster! A whole class of possibilities open up at that point.

For me it sounds a lot like data-driven programming or data-oriented programming.

Thank you for the detailed answer. I am looking into a risk management system and valuation also seems to be an area where data structures can significantly improve calculation time. Also on my end looking into the role of data structure into enabling two separate optimisation paths, one being the real time latency oriented and the other being the batch throughout oriented. If anyone has seen any work on data structures with focus on this kind of optimisations it would be great. A bit related to the parent discussion, I am looking at graphs with tree views if that makes sense.

The point is that these data structures are highly dependent on the problem you're trying to scale.

I don't think an example of one and the process taken to define it is that helpful, since the skill is about being able to do this for an arbitrary problem. It also probably requires a lot of trial and error.

> I need to split up my problem into spaces that don't require synchronization/serialisation.

When I first got a dual CPU (before "cores" were a thing) computer, I decided I'd try dipping my feet in some "proper" parallel coding.

I started with something simple, parallelizing a quicksort routine. This seemed quite trivial: instead of recursing, add the spans to be sorted to a list. I then spawned a thread per CPU, which fetched a span from the list, did a single quicksort pass on it and added up to two new spans to the list. Rinse repeat until list was empty.

Since each span was non-overlapping, the threads only had to synchronize while accessing the list of tasks.

When benchmarking it became clear that while there was a good performance win for large arrays, for short arrays the multithreaded code was much slower than the non-multithreaded version. At my hardware the threshold was around 50k items for integer elements and 20k or so for string elements, IIRC.

I added a threshold detection, where the thread would do a regular recursive quicksort on the span if the length was below the threshold, and this yielded significantly better results.

And with that the harsh reality of multithreading hit me: no free lunch. It was clear the threshold varies not just with element type (slow/complex comparators would reduce the threshold, and vice versa) but with the details of the hardware. So a hardcoded threshold was out of the picture, and it would have to be dynamically determined at runtime.

Was a great learning experience though.

For those who might wonder why, the quicksort splits the array into half and then repeats on the two halves.

Thus the majority of spans are small and quickly processed, and hence the naive multithreaded version leads to lock contention as the threads fight to access the shared list of spans.

The basic algorithm of A* is very sequential, isn't it? It works by taking the best scoring unexpanded node and expand that. Most of the time, there's only one such node. When expansion has finished, you need to re-sort the queue/heap of unexpanded nodes. All those steps are sequential. So I guess the only gain is when the node expansion can be done in parallel; expanding the top-N nodes probably is counterproductive for many problems. How much you gain then depends on the time expansion takes. The advantage of parallelism then depends on how much time one step "down" takes.

This is correct, and Bellman-Ford, while naive compared to A*, actually parallelizes much better. That said, an optimized Bellman-Ford doesn't even resemble the original, naive version of the algorithm.

Yes, I think I can take advantage of my particular problem to parallelise, which I'm still trying to work out.

My neighbour scanning is dynamic and my neighbours and all neighbours from a node is independent from that point forwards, it shall not visit the exact same node. In essence my problem is kind of a tree.

I am trying to infer data flow between two states including hidden states such as functions calls. My dream is that I can provide a start state and end state and the computer writes itself based on type information and data flow analysis of values.

Here's my input data - which is what memory is set to and what registers are set to.

  start_state = {
    "memory": [0, 0, 0, 0],
    "rax": 0,
    "rbx": 1,
    "rcx": 2,
    "rdx": 3,
    "rsp": -1,
    "rdi": -1,
    "rbp": -1
  }

  end_state = {
    "memory": [3, 1, 2, -1],
    "rax": 3,
    "rbx": 2,
    "rcx": 1,
    "rdx": 0,
    "rsp": 6,
    "rdi": -1,
    "rbp": -1
  }

  # these functions take in a value and return another value
  minus_1_to_four = Function("minus1", -1, 4)
  four_to_five = Function("fourtofive", 4, 5)
  five_to_six = Function("fivetosix", 5, 6)

This synthesises the following program in 16 seconds (I improved the heuristic function). Function values input and output can be in any register, but in my example they are all in the same register. With 3 processes it synthesises in 0.6 seconds.

  [start, mov %rax, (%rdx), mov %rbx, (%rbx), mov %rcx, (%rcx), mov %rdx, (%rsp), mov %rax, %rbp, mov %rdx, %rax, mov %rbp, %rdx, mov %rcx, %rbp, mov %rbx, %rcx, mov %rbp, %rbx, call minus1(rsp=-1) -> rsp=4, mov $-1, %rbp, call fourtofive(rsp=4) -> rsp=5, call fivetosix(rsp=5) -> rsp=6]

I wouldn't say sequential. Maybe at implementations are sequential and state based because games need to pause the process on a frame refresh.

A* is naturally recursive [1] and so can be parallelized as you go further.

[1] unless I'm mistaking some other algorithm for A*, each new recursive call of all the neighbours can be started on a different thread or node.

When I was noodling with the Traveling Salesman problem, I was sure that what I really needed was to spend X% of available resources on the Big Gamble (a low probability algorithm with fast results), Y% on a common heuristic and the rest on the honest work of plowing through the linear equations progressively culling the remaining scenarios that need to be tested. I had limited success with this though. I just haven’t done enough LP to make anything noteworthy, and it was a tool sharpening exercise, which made me a little more effective at more mundane batch processing tasks, not a great mind of NP-completeness.

FYI, there are lots of papers on parallel shortest path algorithms. If an approximate solution suffices, there’s also a lot of research available on that, often with some parameter that lets you trade more computation for a tighter approximation. It's not a problem that parallelises particularly well though, so not sure if you'll see good gains in practice.

If you can restrict the structure of your graphs (e.g. planar) then some very efficient methods exist.

Isn't a tree just a graph that is directed and acyclic (DAG)?

So a tree is just a subtype of a graph?

A tree is a subtype of graph. However, a DAG is not a tree if it has cycles once you forget direction, meaning paths can join up again after splitting. This distinction matters because when different paths "join up" again, there is often complicated data duplication/integration that is necessary in order order to combine the results. On a distributed system, it may mean data passing over a network, which you want to avoid.

A tree is a subtype of a graph, but it is not the same as a DAG. A diamond-shaped directed graph (edges A->B, A->C, B->D, C->D) is a DAG, but not a tree.

In graph theory, trees are undirected. In computing, trees usually have two features that differentiate them from their more minimal graph theoretical cousins: they are (a) directed and (b) rooted (a particular vertex is designated as the root, and every vertex can be walked to from that vertex).

But yeah. Some graphs are trees. And you can construct trees within graphs for efficiently navigating connected graphs, which is done in various important and famous algorithms.

Can you share any of the parallel A* code? I’m currently looking at using A* for use in generative design and am pretty ignorant about parallelising code. Would love to learn more!

I've taken a very naive approach and it does NOT scale. It uses python multiprocessing. I think the fScore updates pickling and serialization - communication and synchronization lock overhead is slowing it down. It simply does not parallelise.

This is my code generator/program synthesiser, it synthesises assembly instructions from two given states of memory and registers to take it from one to the other, including hidden states such as functions.

https://replit.com/@Chronological/SlidingPuzzle3#main.py

Thanks, regardless of ability to parallelise it looks interesting.

I've changed the algorithm to not send fScore updates and treat each branch as independent.

This speeds it up from 16 seconds to 320 milliseconds. I am thinking how to make the algorithm scale, by creating better and alternative program candidates in each thread.

This is exactly a reason why I like Scylla as a database. One shard per CPU. Each shard owning different partition of data. Great performance.

I'd like your opinion: channels or locks?

This is really for a program I'm writing in Nim, so perhaps it depends on how channels are implemented?