3 ms·

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

by cgio 3y ago

asimpletune 3y ago
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.
- dlisboa 3y ago
  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).
  - tharkun__ 3y ago
    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?
    - dlisboa 3y ago
      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.
  - eterm 3y ago
    Perhaps you're thinking of Matt Parker's (of standup maths and numberphile fame) video: https://m.youtube.com/watch?v=c33AZBnRHks https://m.youtube.com/watch?v=c33AZBnRHks
    - dlisboa 3y ago
      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.
- sobkas 3y ago
  For me it sounds a lot like data-driven programming or data-oriented programming.
- cgio 3y ago
  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.
ZephyrBlu 3y ago
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.

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

by cgio 3y ago

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

asimpletune 3y ago

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.

dlisboa 3y ago
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).
- tharkun__ 3y ago
  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?
  - dlisboa 3y ago
    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.
- eterm 3y ago
  Perhaps you're thinking of Matt Parker's (of standup maths and numberphile fame) video: https://m.youtube.com/watch?v=c33AZBnRHks https://m.youtube.com/watch?v=c33AZBnRHks
  - dlisboa 3y ago
    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.
sobkas 3y ago
For me it sounds a lot like data-driven programming or data-oriented programming.
cgio 3y ago
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.

ZephyrBlu 3y ago

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.