6 ms·

This old dev has been around to witness the transition from in-depth algorithm development to algorithms as commodities. I've pounded out my share of B-tree sea

This old dev has been around to witness the transition from in-depth algorithm development to algorithms as commodities. I've pounded out my share of B-tree search, polygon intersection, and numeric stuff. Try doing numeric stuff reliably and quickly on a tiny computer without a Floating Point Unit and you'll know why you might need to learn, and then program, Jack Bresenham's line-drawing and circle-drawing algorithms. And there's Newton and Raphson's sqrt(). Hint: if you understand your data and your precision requirement, you can avoid iterating it all the way out to the end of your integer precision, and get a lot more work done. Try transposing a 4-megabyte matrix before the week is out on a machine with 32KiB of RAM and two 5-megabyte hard drives. Yes, it can be done. When I started doing this work it took deep understanding to get anything done. Now it takes the skills of a good reference librarian. We have to be able to find stuff (via npm, nuget, maven) quickly, assess its quality, and figure out how to use it. So the type of thinking we need has changed from "deep" to "broad".

C1sc0cat 6y ago
This was true to an extent in the 70's - I recall us using subroutines from NAG htps://www.nag.co.uk/ Not much point in implementing our own Fourier code.
- crawlcrawler 6y ago
  Not much chance of us seeing an improvements in Fourier transform implementations, then.
  - C1sc0cat 6y ago
    Depends is it better for NAG to do that research or for us to do it? Our funding was to do xxx research and not go off and build a better Fourier transform in this case. Though I do regret that we couldn't get funding to do Vision /ML on one project in the 80's truly cutting edge stuff
  - derefr 6y ago
    And yet we still do, and it's interesting why we do. Most software, we optimize to make it more legible to the compiler. But some software—software we don't trust ourselves to optimize without changing its meaning—we leave alone, and then instead we optimize the compiler specifically to compile that kind of software into better object code. This is what happens with maths code (usually in FORTRAN) and the FORTRAN compilers that work on them. We don't improve the Fourier-transform implementation; we just teach the compiler how to take the "textbook" implementation we've got, and do ever-fancier things to it. Of course, one could also improve the Fourier transform's design—but that requires a mathematician, not a software engineer. Nobody's going to come up with an algorithm with entirely-better time/space complexities just by noodling around in an editor with the existing one. They've got to start from scratch with new maths, derive new theorems, write a textbook implementation of that, and then contribute it to the codebase. And then we'll start a new cycle of getting the compiler to optimize that textbook code.
    - hef19898 6y ago
      Back in 2008 (?), I was in aerospace. The big thing at that time was to become a "systems integrator" instead of a manufacturer. Obviously, while sound on the surface, the OEMs still are manufacturers today. With a higher degree of integration of third party systems, e.g. radar an so on. Today, the same logic can be applied to all the Xaas business models out there. SaaS, PaaS, algorythms, it seems that there could be two extremes. On the one end you have companies developing the services, on the other you have businesses excelling at combining these services.
mlthoughts2018 6y ago
I disagree somewhat. For example in my freshman year of college I took a numerical analysis class that covered Newton-Raphson, Brent’s method, advanced quadrature, Runge-Kutta, preconditioning, all sorts of matrix linsolve, LU, rotation matrix, inversion stuff, floating point byte structure, and various topics in parallel computing like Amdahl’s law. It was intense and very detailed, with a lot of discussion of how these issues arise in and how to write these algorithms in the C language and also in Python (like, in C extension modules of CPython). My first job out of college was in a defense research lab that had projects running on tons of simulation systems, radar systems, hardware and embedded systems for vehicles used in the military. What I learned later when I went back to grad school and worked more mainstream tech product jobs is that in those “hardcore numerical computing” situations, there is often a complete absence of architecture or design, no framing the problem in terms of the customer or success criteria, too much willingness to reinvent wheels, constant belief that build it is always better than buy it. From a technical point of view, there was also a gaping absence of statistics, especially statistical optimization techniques like with Markov chains and simulated annealing. There was a certain chip on people’s shoulder that hard core graph algorithms or hard core data structure based search was “real programming” when you could solve the same problem with simulated annealing in 1/100 the amount of code, as long as you didn’t parochially think your numerics experience was superior and force a solution that way. Even though my peers were really experienced, it felt like there was an inverse relationship between numerical algorithm thinking and creative problem solving thinking. Hard core algorithms just sucked all the air out of the room, without making projects more successful.
bobmaxup 6y ago
I think the enterprise to open source software relationship today is somewhat similar to the concept of convergence in economics. https://en.wikipedia.org/wiki/Convergence_(economics) https://en.wikipedia.org/wiki/Convergence_(economics)
game_the0ry 6y ago
As a young dev, I would be very interested in your opinions and experiences. Specifically, in book or blog format, maybe tweet format :D
- hoorayimhelping 6y ago
  I know you meant this harmlessly and maybe even encouragingly, but this post comes off as pretty entitled. It comes off kind of like, "hey, I want access to your knowledge and wisdom, but I want you to do an enormous amount of work to put it into a format that is easy for me to consume at my leisure. plzkthxbye." Usually when you want to learn from someone more experienced than you, you seek them out, and you do the work to understand their wisdom, not the other way around. Plato didn't ask Socrates to write everything down so he could read it and grow, Plato studied under Socrates and did the work of transcribing his words himself for the future.
  - vharuck 6y ago
    I read it as, "Do you have a blog? If not, have you thought about blogging?" Nothing demanding. Especially with the happy emoji at the end.
    - game_the0ry 6y ago
      Basically, this. :)
  - game_the0ry 6y ago
    > It comes off kind of like, "hey, I want access to your knowledge and wisdom, but I want you to do an enormous amount of work to put it into a format that is easy for me to consume at my leisure. plzkthxbye." Kind of. When guys like OJ write books, I buy them. When they blog / tweet, I re-tweet them. Mostly to share knowledge with my industry peers and other newbs, but also to support directly or indirectly. I don't see this as one-sided and I don't see anything wrong with expecting something in returning for sharing knowledge. I will tell you what disappoints me - when good knowledge is lost over time. Or worse, hoarded and lost anyway. And I will tell you what else is disappoints me - people who assume young newbs have an entitlement complex when seeking out knowledge, let alone encouraging others to share knowledge. You strike me as a 'what's in it for me?' type of person. That's ok, I might buy your blog or read your book if you have them.
GuiA 6y ago
It all depends what kind of work you do. I do things that touch embedded hardware and graphics and frequently find myself doing exactly the sort of things you described. If you miss it, it's certainly not gone :) (and I made a conscious decision to build my career around this, rather than fishing for npm modules).
chrisseaton 6y ago
> Try transposing a 4-megabyte matrix before the week is out on a machine with 32KiB of RAM and two 5-megabyte hard drives. Transposing is just copying bytes from one place to another, isn't it? There's no maths involved, is there? To have that run in a week with the most naive approach possible you'd only need a machine that can copy seven words a second. Are there real relevant machines that can't do that? What algorithms could help you anyway? Something to do with cache and the order in which you read and write? And you've got plenty of space as you can trivially do it in-place.
- smallnamespace 6y ago
  The RAM here is essentially a cache. You’ll want to transpose a block at a time, something like 150 x 150 blocks, so it all fits. Each block is not contiguous on disk, so you’ll want to load blocks in the right order to avoid extra seeks.
  - deleted 6y ago
    [deleted]
  - deleted 6y ago
    [deleted]
  - chrisseaton 6y ago
    I suspect, since the poster mentioned having two hard drives, that really they're confusing transposition with inversion. These aren't the same things.
- dekhn 6y ago
  Transposing is copying bytes, but changing the stride order of the array. So a lot of the work is extremely non-local. The poster meant that to do this efficiently, you'll use blocks and stage data between the drives while working. You can also transpose in place: https://en.wikipedia.org/wiki/In-place_matrix_transposition https://en.wikipedia.org/wiki/In-place_matrix_transposition see some of the commentary on efficiency there.
EGreg 6y ago
Well, there’s the coming up with an algorithm Then there is the teaching it in schools to new comp sci people, as part of a curriculum designed to help you understand basic principles Then there are implementations on various environments, constant optimizations, witness the JS engine wars for instance People specialize in their own industryon various niches — primitives, or combining primitives, etc. And algorithms are just one part of an industry! How many of you want to invent your own SHA1 or BLS signatures LOL You just use them and they have documented properties and guarantees. These are building blocks people use. This thing about glorifying algorithms is sort of an “applied maths” mentality. And models like Black-Scholes therefore become taught everywhere and become self-fulfilling prophecies. But really, math is just a very simplified version of computing and modeling. People operate with maybe 10-20 symbols throughout the entire thing. There are many things — like the game of life and New Kind of Science - that you can’t describe in analytic form.

C1sc0cat 6y ago

This was true to an extent in the 70's - I recall us using subroutines from NAG htps://www.nag.co.uk/ Not much point in implementing our own Fourier code.

crawlcrawler 6y ago
Not much chance of us seeing an improvements in Fourier transform implementations, then.
- C1sc0cat 6y ago
  Depends is it better for NAG to do that research or for us to do it? Our funding was to do xxx research and not go off and build a better Fourier transform in this case. Though I do regret that we couldn't get funding to do Vision /ML on one project in the 80's truly cutting edge stuff
- derefr 6y ago
  And yet we still do, and it's interesting why we do. Most software, we optimize to make it more legible to the compiler. But some software—software we don't trust ourselves to optimize without changing its meaning—we leave alone, and then instead we optimize the compiler specifically to compile that kind of software into better object code. This is what happens with maths code (usually in FORTRAN) and the FORTRAN compilers that work on them. We don't improve the Fourier-transform implementation; we just teach the compiler how to take the "textbook" implementation we've got, and do ever-fancier things to it. Of course, one could also improve the Fourier transform's design—but that requires a mathematician, not a software engineer. Nobody's going to come up with an algorithm with entirely-better time/space complexities just by noodling around in an editor with the existing one. They've got to start from scratch with new maths, derive new theorems, write a textbook implementation of that, and then contribute it to the codebase. And then we'll start a new cycle of getting the compiler to optimize that textbook code.
  - hef19898 6y ago
    Back in 2008 (?), I was in aerospace. The big thing at that time was to become a "systems integrator" instead of a manufacturer. Obviously, while sound on the surface, the OEMs still are manufacturers today. With a higher degree of integration of third party systems, e.g. radar an so on. Today, the same logic can be applied to all the Xaas business models out there. SaaS, PaaS, algorythms, it seems that there could be two extremes. On the one end you have companies developing the services, on the other you have businesses excelling at combining these services.

mlthoughts2018 6y ago

I disagree somewhat. For example in my freshman year of college I took a numerical analysis class that covered Newton-Raphson, Brent’s method, advanced quadrature, Runge-Kutta, preconditioning, all sorts of matrix linsolve, LU, rotation matrix, inversion stuff, floating point byte structure, and various topics in parallel computing like Amdahl’s law. It was intense and very detailed, with a lot of discussion of how these issues arise in and how to write these algorithms in the C language and also in Python (like, in C extension modules of CPython). My first job out of college was in a defense research lab that had projects running on tons of simulation systems, radar systems, hardware and embedded systems for vehicles used in the military. What I learned later when I went back to grad school and worked more mainstream tech product jobs is that in those “hardcore numerical computing” situations, there is often a complete absence of architecture or design, no framing the problem in terms of the customer or success criteria, too much willingness to reinvent wheels, constant belief that build it is always better than buy it. From a technical point of view, there was also a gaping absence of statistics, especially statistical optimization techniques like with Markov chains and simulated annealing. There was a certain chip on people’s shoulder that hard core graph algorithms or hard core data structure based search was “real programming” when you could solve the same problem with simulated annealing in 1/100 the amount of code, as long as you didn’t parochially think your numerics experience was superior and force a solution that way. Even though my peers were really experienced, it felt like there was an inverse relationship between numerical algorithm thinking and creative problem solving thinking. Hard core algorithms just sucked all the air out of the room, without making projects more successful.

bobmaxup 6y ago

I think the enterprise to open source software relationship today is somewhat similar to the concept of convergence in economics. https://en.wikipedia.org/wiki/Convergence_(economics) https://en.wikipedia.org/wiki/Convergence_(economics)

game_the0ry 6y ago

As a young dev, I would be very interested in your opinions and experiences. Specifically, in book or blog format, maybe tweet format :D

hoorayimhelping 6y ago
I know you meant this harmlessly and maybe even encouragingly, but this post comes off as pretty entitled. It comes off kind of like, "hey, I want access to your knowledge and wisdom, but I want you to do an enormous amount of work to put it into a format that is easy for me to consume at my leisure. plzkthxbye." Usually when you want to learn from someone more experienced than you, you seek them out, and you do the work to understand their wisdom, not the other way around. Plato didn't ask Socrates to write everything down so he could read it and grow, Plato studied under Socrates and did the work of transcribing his words himself for the future.
- vharuck 6y ago
  I read it as, "Do you have a blog? If not, have you thought about blogging?" Nothing demanding. Especially with the happy emoji at the end.
  - game_the0ry 6y ago
    Basically, this. :)
- game_the0ry 6y ago
  > It comes off kind of like, "hey, I want access to your knowledge and wisdom, but I want you to do an enormous amount of work to put it into a format that is easy for me to consume at my leisure. plzkthxbye." Kind of. When guys like OJ write books, I buy them. When they blog / tweet, I re-tweet them. Mostly to share knowledge with my industry peers and other newbs, but also to support directly or indirectly. I don't see this as one-sided and I don't see anything wrong with expecting something in returning for sharing knowledge. I will tell you what disappoints me - when good knowledge is lost over time. Or worse, hoarded and lost anyway. And I will tell you what else is disappoints me - people who assume young newbs have an entitlement complex when seeking out knowledge, let alone encouraging others to share knowledge. You strike me as a 'what's in it for me?' type of person. That's ok, I might buy your blog or read your book if you have them.

GuiA 6y ago

It all depends what kind of work you do. I do things that touch embedded hardware and graphics and frequently find myself doing exactly the sort of things you described. If you miss it, it's certainly not gone :) (and I made a conscious decision to build my career around this, rather than fishing for npm modules).

chrisseaton 6y ago

> Try transposing a 4-megabyte matrix before the week is out on a machine with 32KiB of RAM and two 5-megabyte hard drives. Transposing is just copying bytes from one place to another, isn't it? There's no maths involved, is there? To have that run in a week with the most naive approach possible you'd only need a machine that can copy seven words a second. Are there real relevant machines that can't do that? What algorithms could help you anyway? Something to do with cache and the order in which you read and write? And you've got plenty of space as you can trivially do it in-place.

smallnamespace 6y ago
The RAM here is essentially a cache. You’ll want to transpose a block at a time, something like 150 x 150 blocks, so it all fits. Each block is not contiguous on disk, so you’ll want to load blocks in the right order to avoid extra seeks.
- deleted 6y ago
  [deleted]
- deleted 6y ago
  [deleted]
- chrisseaton 6y ago
  I suspect, since the poster mentioned having two hard drives, that really they're confusing transposition with inversion. These aren't the same things.
dekhn 6y ago
Transposing is copying bytes, but changing the stride order of the array. So a lot of the work is extremely non-local. The poster meant that to do this efficiently, you'll use blocks and stage data between the drives while working. You can also transpose in place: https://en.wikipedia.org/wiki/In-place_matrix_transposition https://en.wikipedia.org/wiki/In-place_matrix_transposition see some of the commentary on efficiency there.

EGreg 6y ago

Well, there’s the coming up with an algorithm Then there is the teaching it in schools to new comp sci people, as part of a curriculum designed to help you understand basic principles Then there are implementations on various environments, constant optimizations, witness the JS engine wars for instance People specialize in their own industryon various niches — primitives, or combining primitives, etc. And algorithms are just one part of an industry! How many of you want to invent your own SHA1 or BLS signatures LOL You just use them and they have documented properties and guarantees. These are building blocks people use. This thing about glorifying algorithms is sort of an “applied maths” mentality. And models like Black-Scholes therefore become taught everywhere and become self-fulfilling prophecies. But really, math is just a very simplified version of computing and modeling. People operate with maybe 10-20 symbols throughout the entire thing. There are many things — like the game of life and New Kind of Science - that you can’t describe in analytic form.