5 ms·

I often find myself thinking: "But how would I do any of these without reaching for mutation? So that I can later parallelize them?" And then I come up empty. I

I often find myself thinking: "But how would I do any of these without reaching for mutation? So that I can later parallelize them?" And then I come up empty. I still need to work through "Purely Functional Data Structures" by Okasaki. Hopefully then I will have an idea, of how to come up with a functional version to mostly single-core algorithms or at least locking-requiring algorithms. I skipped ahead once and looked at functional red-black trees and the solution was to involve one more color! How ingenious is that?! I have no idea, how people got to these solutions. In many places algorithms are described implicitly with mutation assumed. However, this can be very hard to parallelize later and might hit you in the future. In the times of many cores, this seems no longer appropriate to me. I wish we spent more time on learning how to get it done without mutation. Another great post that was linked at some point on HN was this: https://nullprogram.com/blog/2020/04/30/ https://nullprogram.com/blog/2020/04/30/ -- A comparatively simple change in approach and yet it allows for massive parallelization without locks! This is the kind of stuff we should learn more about and then make more use of our many available cores, moving on from the single core world of algorithms.

samsquire 4y ago
I am deeply interested in parallelism. Would enjoy talking to you about it. I think the parallelism provided by Haskell is really interesting. And its software transactional memory. I think parallelisation can be generalised but we need to study it further to understand it better. There must be a set of primitives that parallelise very well but they've not been found out yet. Rather than trying to parallelise something that was invented to be sequential, we parallelise something that is parallelisable. I'm today working on parallelising a total ordered list view over X sorted lists that are maintained by separate threads or independent computer servers. My idea is to use N way mergesort to retrieve up to N items sorted items. Servicing requests is extremely fast since there is no synchronization needed within a thread or server but if you need total order, you need to use the N way mergesort. I'm thinking you have a cluster for ordered views and a cluster for within-a-thread view. My other problem I'm working on is how to paralellise integer updates. If you have 8000000000 accounts (which DOES fit on a single machine) but you have more operations overall than a single machine can process? You could shard by account but I think there's an approach that shards by integer and per server. You store a portion of the integer on each machine, hopefully enough to handle operations. Then when you need to check if account integer > deduction amount I just need to learn how to a strongly consistent read cheaply. Essentially we load balance the integer in the account. For example, fibonacci is often used as an example to parallelise something but it's never implemented in a parallelisable manner. It just does the same calculation in different threads. If we knew the formula of fibonacci that didn't depend on previous iterations, we could parallelise fibonacci. But I'm not a mathematician so I I'm not sure how to find out that formula.
- Jensson 4y ago
  Sorting is a standard distributed algorithm, it is basically quicksort but you move some data between servers between the steps. The aim is to create ordered buckets of data that you then send to servers. The first step is to find good pivots, so sort the data and select data points at the median and different percentiles from each server, then fan out those pivot candidates to every server. Now since all servers has the same pivots they can create the same buckets, and send the data they have of each bucket to the corresponding server. The buckets wont have perfect balance, so you typically want a few times more buckets than you have servers to ensure that you don't overload one of them, that is the fast way. Alternatively you can do another fan out step computing the number of items in each bucket among the servers, and split large ones into smaller buckets using the same technique as before, this will always work but requires a bit more communication between the servers. As for distributing heavy computations, Google has done that to compute your search results since almost the beginning. Fan out a request to a huge cluster of servers that all have different parts of their data in ram, then they filter and return the parts of the data that is relevant to you. It is totally possible to do it and return a response to the user in a fraction of a second. Typically it takes a few milliseconds to send data between servers in a data center, you can easily fan out a request to a few hundred servers, let them compute and return something 15 milliseconds later. It costa bit to run that though, Google can afford it since search is worth so much per request, so you got figure out if your usecase is worth that much compute. But it doesn't cost that much more than running the same work on a single server, it depends a bit on how well your servers are collocated. Btw, frameworks for distributed computing like Apache Spark are way too slow for this, you have to hand roll those. But it really isn't that hard to do, there are programming competitions involving those, a correct solution to these kind of things takes like 30 minutes to write if you know what to do and you have done all the boring infrastructure work to ensure you can contact servers and access the data. That is why most programmers never work with complex algorithms, because the boring and tedious work on all the other parts takes up most of the time and manpower.
  - convolvatron 4y ago
    assuming that local access is cheaper than distribution, wouldn't a merge sort be better?
mrkeen 4y ago
Often mutation on a single core is faster than persistence on multiple cores.
- samsquire 4y ago
  This is the problem I'm working on. Independent threads are as independently fast as a single core and they slow down overall when synchronization is introduced. Amdahls law means that the cost of sequential tasks approaches the majority of time compared to the parallel speed up. My design is to shard by thread. Each thread or machine maintains a sorted shard of the data. Erlang takes a similar approach. If you want a total order view, then you N way mergesort. I have a lock free algorithm that can do about 1.2 million synchronizations a second across 11 threads. My lock benchmark does 3,444,152 3.4 million requests per second with 11 threads so my lock free algorithm isn't as good as locks. My lock free algorithm doesn't block though. I'm thinking of calibrating message rate by increasing latency to increase throughput and limit interference for the lock. If I increase message rate to 2500-25000 messages then more messages get transferred per synchronization event.
  - srcreigh 4y ago
    How'd you pick 11 threads? How do the algorithms scale as you change # of threads? T=2, 10, 100, 1000, 10k
    - samsquire 4y ago
      https://news.ycombinator.com/item?id=34126789 https://news.ycombinator.com/item?id=34126789 I replied to your comment here.
  - withinboredom 4y ago
    Why merge them at all? Can a lazy merge increase performance by the fact you are usually iterating over them and at that point most work will be done by the iteration and not by the merger. That gives you some time to work out which thread/machine to pull from next while the main thread works on the result of the last iteration (ie, preempt the iteratie). You could even buffer/stream them from each thread much faster than any code could do real work. In my experience, lock-free solutions tend to not do well when threads share a physical core (vs virtual cores), but ymmv.
Jensson 4y ago
You can parallelize with mutations, just split the data and do a tiny bit of extra work when the data overlaps. There aren't that many real world cases where you want to run expensive computations on highly connected data, and in those cases you mostly just write GPU code instead of bothering with functional CPU languages. That is what the engineers who works on the extreme end of performance does, if you want to learn functional programming that is efficient and performant then go and learn GPU programming, the techniques you learn there also works for many CPU applications, there are decades of top end industry practices behind those techniques.
- zelphirkalt 4y ago
  There is certainly some kind of middle ground between single core CPU and massive parallelization on a GPU. What am I going to use my 16 CPU cores for? Should they sit idle forever, only ever handing parallel work over to the GPU? Also not all work is parallelizable in the way graphics are parallelizable or follow the relatively simple fork-join structure. What about things like actor systems, where each actor may run on another core, each doing different kind of work? Sometimes one might want to also have good single core performance in parallelized settings, so that the work for a single core gets finished quickly. I am not convinced the picture is really as black and white as "do parallelized things on GPU, single core things on CPU".
senderista 4y ago
Okasaki’s book is generally not practical and he even expressed some surprise at its popularity due to that fact. There are some practical purely functional data structures but you’ll have to find them elsewhere.
- zelphirkalt 4y ago
  Can you go into a bit more detail, of why it would not be practical? Are there better implementations of the data structures in the book? The book I believe is from 1995 or so, so I could well imagine, that in the meantime progress has been made. But what exactly makes the algorithms in the book impractical for usage within a functional program?

samsquire 4y ago

I am deeply interested in parallelism. Would enjoy talking to you about it. I think the parallelism provided by Haskell is really interesting. And its software transactional memory. I think parallelisation can be generalised but we need to study it further to understand it better. There must be a set of primitives that parallelise very well but they've not been found out yet. Rather than trying to parallelise something that was invented to be sequential, we parallelise something that is parallelisable. I'm today working on parallelising a total ordered list view over X sorted lists that are maintained by separate threads or independent computer servers. My idea is to use N way mergesort to retrieve up to N items sorted items. Servicing requests is extremely fast since there is no synchronization needed within a thread or server but if you need total order, you need to use the N way mergesort. I'm thinking you have a cluster for ordered views and a cluster for within-a-thread view. My other problem I'm working on is how to paralellise integer updates. If you have 8000000000 accounts (which DOES fit on a single machine) but you have more operations overall than a single machine can process? You could shard by account but I think there's an approach that shards by integer and per server. You store a portion of the integer on each machine, hopefully enough to handle operations. Then when you need to check if account integer > deduction amount I just need to learn how to a strongly consistent read cheaply. Essentially we load balance the integer in the account. For example, fibonacci is often used as an example to parallelise something but it's never implemented in a parallelisable manner. It just does the same calculation in different threads. If we knew the formula of fibonacci that didn't depend on previous iterations, we could parallelise fibonacci. But I'm not a mathematician so I I'm not sure how to find out that formula.

Jensson 4y ago
Sorting is a standard distributed algorithm, it is basically quicksort but you move some data between servers between the steps. The aim is to create ordered buckets of data that you then send to servers. The first step is to find good pivots, so sort the data and select data points at the median and different percentiles from each server, then fan out those pivot candidates to every server. Now since all servers has the same pivots they can create the same buckets, and send the data they have of each bucket to the corresponding server. The buckets wont have perfect balance, so you typically want a few times more buckets than you have servers to ensure that you don't overload one of them, that is the fast way. Alternatively you can do another fan out step computing the number of items in each bucket among the servers, and split large ones into smaller buckets using the same technique as before, this will always work but requires a bit more communication between the servers. As for distributing heavy computations, Google has done that to compute your search results since almost the beginning. Fan out a request to a huge cluster of servers that all have different parts of their data in ram, then they filter and return the parts of the data that is relevant to you. It is totally possible to do it and return a response to the user in a fraction of a second. Typically it takes a few milliseconds to send data between servers in a data center, you can easily fan out a request to a few hundred servers, let them compute and return something 15 milliseconds later. It costa bit to run that though, Google can afford it since search is worth so much per request, so you got figure out if your usecase is worth that much compute. But it doesn't cost that much more than running the same work on a single server, it depends a bit on how well your servers are collocated. Btw, frameworks for distributed computing like Apache Spark are way too slow for this, you have to hand roll those. But it really isn't that hard to do, there are programming competitions involving those, a correct solution to these kind of things takes like 30 minutes to write if you know what to do and you have done all the boring infrastructure work to ensure you can contact servers and access the data. That is why most programmers never work with complex algorithms, because the boring and tedious work on all the other parts takes up most of the time and manpower.
- convolvatron 4y ago
  assuming that local access is cheaper than distribution, wouldn't a merge sort be better?

mrkeen 4y ago

Often mutation on a single core is faster than persistence on multiple cores.

samsquire 4y ago
This is the problem I'm working on. Independent threads are as independently fast as a single core and they slow down overall when synchronization is introduced. Amdahls law means that the cost of sequential tasks approaches the majority of time compared to the parallel speed up. My design is to shard by thread. Each thread or machine maintains a sorted shard of the data. Erlang takes a similar approach. If you want a total order view, then you N way mergesort. I have a lock free algorithm that can do about 1.2 million synchronizations a second across 11 threads. My lock benchmark does 3,444,152 3.4 million requests per second with 11 threads so my lock free algorithm isn't as good as locks. My lock free algorithm doesn't block though. I'm thinking of calibrating message rate by increasing latency to increase throughput and limit interference for the lock. If I increase message rate to 2500-25000 messages then more messages get transferred per synchronization event.
- srcreigh 4y ago
  How'd you pick 11 threads? How do the algorithms scale as you change # of threads? T=2, 10, 100, 1000, 10k
  - samsquire 4y ago
    https://news.ycombinator.com/item?id=34126789 https://news.ycombinator.com/item?id=34126789 I replied to your comment here.
- withinboredom 4y ago
  Why merge them at all? Can a lazy merge increase performance by the fact you are usually iterating over them and at that point most work will be done by the iteration and not by the merger. That gives you some time to work out which thread/machine to pull from next while the main thread works on the result of the last iteration (ie, preempt the iteratie). You could even buffer/stream them from each thread much faster than any code could do real work. In my experience, lock-free solutions tend to not do well when threads share a physical core (vs virtual cores), but ymmv.

Jensson 4y ago

You can parallelize with mutations, just split the data and do a tiny bit of extra work when the data overlaps. There aren't that many real world cases where you want to run expensive computations on highly connected data, and in those cases you mostly just write GPU code instead of bothering with functional CPU languages. That is what the engineers who works on the extreme end of performance does, if you want to learn functional programming that is efficient and performant then go and learn GPU programming, the techniques you learn there also works for many CPU applications, there are decades of top end industry practices behind those techniques.

zelphirkalt 4y ago
There is certainly some kind of middle ground between single core CPU and massive parallelization on a GPU. What am I going to use my 16 CPU cores for? Should they sit idle forever, only ever handing parallel work over to the GPU? Also not all work is parallelizable in the way graphics are parallelizable or follow the relatively simple fork-join structure. What about things like actor systems, where each actor may run on another core, each doing different kind of work? Sometimes one might want to also have good single core performance in parallelized settings, so that the work for a single core gets finished quickly. I am not convinced the picture is really as black and white as "do parallelized things on GPU, single core things on CPU".

senderista 4y ago

Okasaki’s book is generally not practical and he even expressed some surprise at its popularity due to that fact. There are some practical purely functional data structures but you’ll have to find them elsewhere.

zelphirkalt 4y ago
Can you go into a bit more detail, of why it would not be practical? Are there better implementations of the data structures in the book? The book I believe is from 1995 or so, so I could well imagine, that in the meantime progress has been made. But what exactly makes the algorithms in the book impractical for usage within a functional program?