1. 3

    These are some good tips. I recently have added more of this sort of rigor to my development process, with basically the realization that I don’t want to known as they guy who turns over code that breaks in an obvious case.

    1. 1

      Yea, it’s mortifying to have to explain that to your team / boss / customers. The programming equivalent of a terrible typo in a mass email.

    1. 14

      Given the same task, two developers often come up with solutions that differ in an order of magnitude in size, complexity, dependency count and resource consumption.

      I have witnessed that over and over.

      1. 3

        In what kind of setting do two developers have to produce the exact same thing at the same time, without talking to eachother about it? And is it always the case that developer A produces something that’s objectively 10x better than developer B, or are the roles sometimes reversed. For instance, does it depend on experience in a certain niche?

        1. 4

          That happens all the time when discussing the scope of new projects.

          A recent example I have in mind is, the employer wants a place to collect and analyze data that is being generated by their product.

          • Developer A’s proposal was to build a full data warehouse with SMT, CMT, ETL, Timeseries DB, …
          • Developer B’s proposal was to ingest the data into an S3 bucket in a regular format, and then plug whatever DB we need when we need it.

          Without judging which proposal is the most appropriate, which varies on the context. It’s quite obvious to me that the first proposal is at least 10x bigger.

          1. 2

            One example are test-work situations. Multiple developers who are considered for longer term projects do the same small project.

            I did not say objectively better. But 10x difference in size, complexity, dependency count and resource consumption. Personally, I think this leads to even more then 10x slower progress when the code evolves. But opinions on this differ widely.

            1. 2

              But 10x difference in size, complexity, dependency count and resource consumption.

              I would probably call that objectively better. But maybe that’s my own biased thinking.

              For instance, did the developers know that optimizing for these things was a goal? Did the other developers produce something in shorter time? Were they equally experienced?

              1. 2

                did the developers know that optimizing for these things was a goal

                No, because development is a tradeoff between so many goals that stating something like “size is important” would lead to absurd constructs. In my experience, every developer has their style and you cannot change it much. For example a dev who prefers to think in “business objects” over “sql queries” will struggle if you force them to change that type of thinking. Even if their approach creates code that needs ten million times more resources.

                Did the other developers produce something in shorter time?

                I would say usually coding time is shorter for the smaller, leaner, less resource hungry solutions with less dependencies.

                Were they equally experienced?

                In my experience there is a strong correlation betwen experience and the type of solutions a developer comes up with. And the time they need to implement them. More experienced developers tend to come up with leaner solutions and need less time to implement them.

                1. 2

                  In my experience there is a strong correlation betwen experience and the type of solutions a developer comes up with. And the time they need to implement them.

                  This would seem to fit well with other types of jobs. I think the myth is that there are people who are “magically” 10x better somehow, which makes very little sense to me.

                  1. 5

                    It’s not that they’re magically better. There are practices you can follow that get you those results, but people just don’t seem interested in following them:

                    • Understand the business reasoning behind the project…look for ways of exploiting that knowledge to minimize the amount of work done.
                    • Less code is always easier to debug…or if you can’t debug, throw out and replace.
                    • Clearly defined project goals and constraints and milestones make development fast and visible.
                    • Throwaway prototypes are faster than big projects and teach you more–and may be good enough for the business.
                    • Understanding, deeply, the tools you use and the basic principles of computer science and engineering help you prune solution spaces a lot better.
                    • Identify whether or not the framework/third-party app is actually delivering value over just implementing a smaller bespoke solution yourself. Color picker? Almost certainly. Database extension? Probably. Container orchestration for a static blog? Probably not.
                    • Pseudocode and stepwise refinement of the solution to a problem. If you can’t explain something with bullet points, you don’t understand it, and if you don’t understand it, you’re slow.

                    There are more I think, but that’s a start.

                    Somewhat grumpily: there may not be 10x software engineers, but there sure as hell are 10x embedded AWS salesfolk.

                    1. 2

                      I think your third point is the most important one. Perhaps a 10x developer is gifted at recognizing the business priorities even when the Product folks don’t see how much size/complexity matters?

                  2. 2

                    I would like to think that my style has some flexibility to it, though I’ve definitely landed on the SQL queries side of that divide in the past.

                    Of course, everyone struggles with a new way of thinking at first. Which is why, for me at least, I seek out new ways of thinking, so I can get the struggle done with.

                    1. 1

                      I would say usually coding time is shorter for the smaller, leaner, less resource hungry solutions with less dependencies

                      I’m not sure I agree, here. Maybe if you take “coding time” (as opposed to “dev time”) very strictly, but even then…

                      My anecdata includes a bunch of hackathon projects that, when polished up for production, amounted to far less code. Reducing duplication, refining design for smaller code, replacing bespoke with off-the-shelf libraries, etc, all benefit from taking time.

              2. 3

                I code for approximately an hour a day after my kids have gone to bed. (I’m a manager these days, so my job doesn’t involve day-to-day coding.) During that time I can be shockingly productive, cranking out a solid chunk of performant, safe, well-factored code in an amount of time that would have been an extended coffee break back in my “code-slinging” days.

                So, have I discovered the Nirvana of 10x-ness? Could I jump back in to coding and be massively more effective than I was in my 20s or the portion of my 30s where I still considered myself a professional software developer?

                No, and no. I’ve just found a comfortable niche where the problem domain, freedom to choose the tools I want, and lack of 50 competing demands on my time let me go head-down and code and consider only that time when I measure my production.

                In my experience there’s a very strong correlation between “10x coders” and people who are given the space to work, control over their tools, and trust to architect systems as they choose.

                Whether they earn that because of demonstrated, sustained performance or learn to do it after thrashing around in the deep end for a few years is kind of a chicken-and-egg problem, but studies and surveys (sorry to not have links handy, I’m typing this on my phone) show consistently that developers are happiest and feel most effective when offered those freedoms.

              1. 3

                I’d written an article about using Factor a couple years ago, and never really came back to it. It’s a very interesting language, once you get used to the stack-based nature of the basics, though I highly recommend getting familiar with the vocabularies for local variables. They aren’t entirely elegant in the stack-oriented fashion, but they can be quite helpful for when a problem doesn’t fit into a stack neatly (like the quadratic formula), or for as a means of getting you to a place where things can fit neatly on the stack.

                Going to pick it up again for a side-scripting language, and see how it goes.

                1. 4

                  Just to be clear, while we prefer stack-based approaches, we happily use lexical variables even in the core vocabularies when it’s easier. Hell, there’s a full-blown infix syntax that you can use when you need it. One of the great things about Factor is how flexible the syntax is.

                1. 2

                  So, I’m reading through this now, and some of the links to bits of the phoenix source code have fallen out of date. Perhaps they could be replaced with links to fixed commit blobs with line numbers? That being said, it’s super handy to see what’s going on.

                  1. 1

                    Good call. I’ll try to get that fixed up soon.

                  1. 3

                    My main takeaway is that chi is worth looking into. It is faster than gorilla and more powerful than http.ServeMux.

                    1. 3

                      I have used chi, and it is a very pleasant experience as far as Go routers go

                    1. 1

                      I’ve seen Row Level security use to implement a multi-tenant database once with SQL Server, where each table would would have the ID of the tenant in it.

                      I think for application-focused use-cases, most of those ACLs would end up being busywork or part of a defence-in-depth, which is more effort on auth than most projects are willing to expent.

                      1. 3

                        So, you say, towards the end of the vdieo, that all structure is derivative, but I’m struggling to understand the implications of that beyond a general “every needs to be considered in context” sense.

                        1. 2

                          I was telling a friend online today that it’s a struggle trying to find the right pace for the material I have to cover. If I go too fast, people miss the point. Yet if I take my time and establish foundations, people complain it’s too slow. This is a good example of that.

                          Basically there is a system to explain why structure is created, any structure from a database design to a bridge. Although I know that sounds overly-broad, understanding the system that creates structure allows us to start teasing it apart and optimizing it, looking at how we code and architect systems from the outside rather than as people down in the trenches in the heat of battle.

                          Structure has to exhibit some desired behavior and conform to whatever rules you’re carrying around in your head when you create it. Most of these rules are invisible, unconscious even. For instance, I’ve been brought on to the beginnings of large systems being designed only to be given a list of things they’ve already decided to use, no negotiation. That kind of thing can have vast costs and cause vile and pernicious problems downstream … and the folks suffering through it would never know that the org brought this on themselves.

                          Behavior is pretty easy to track. We have behavior we want and we have tests to validate that behavior. (The tests can be formal or just in your head). Rules/Values are another thing entirely. It’s possible to have tests here too, though! So a while later we’ll talk about infrastructure testing, where things like the simian army comes in. But we’ll only do that once we drive out more details about what exactly we mean by rules or values.

                          So I had to start somewhere. One of the interesting things about “all structure is derivative” is how many senior programmers and architects that will dispute it! You have to sit down with them and take them through example-after-example, usually from their own work, for it to finally sink in. When we talk about the modern development environment being overly-complex and systems that are built far beyond what’s needed, the failure to understand this is where it all starts .. and where we can start fixing it.

                          1. 3

                            Expanded out just a hair, it makes a bit more sense. So, to make sure I understand the point, all structures (languages or tools) are shaped by the structure/context that led to their creation. We can take advantage of this knowledge by trying to apply some our systems knowledge one level back.

                            To start with a trivial example, while you can do most tasks with most tools, choosing a tool that is a good fit makes for getting the task done easier. Hammering nails, rather than smashing a screwdriver or a fist into them (or, using Rails or PHP for a website rather than using C++ or CGI/Bash).

                            Taken a level up, architecture choices in a software project, or how many people are working on a given product can have a big influence (Conway’s Law), or the like.

                            Of course, the more levels up you go, the more you switch towards politics and a messy system of people. A messy system of code can come from one person, or from many.

                            Why do you think so many senior software devs are resistant to the idea? Is it pride? Part of the consequences of the software industry having a myopic and incomplete view of its own history?

                            1. 4

                              It’s a weird thing because so much of it we are unable to see. It’s like the old “you can’t explain water to fish” thing.

                              I believed, taught, and preached YAGNI for years. I can’t convey the shock I felt when I finally realized I wasn’t doing it. Yikes!

                              You should be able to point to any piece of code or architecture in your solution and be able to explain why you were forced to have it there. Most of the time people think they can do this, but when pressed it’s just a lot of arm waving and talk about best practices and such.

                              1. 2

                                How did you realize that you weren’t practicing YAGNI? It’s something I’ll admit I don’t adhere to nearly perfectly, (but then, I also admit that I don’t follow any software principle perfectly).

                                I’d like to think I’m somewhat self aware, but I will also admit that I struggle with a lot of patterns that recur and seem less than ideal. But then, I’ve also grown up in a cross cultural setting, so my water has been shifted a lot, which makes me more aware of it in general.

                            2. 2

                              So, are any of these reasonable ways to paraphrase what you mean by “all structure is derivative”?

                              • “No part of a system should be present due to dogma. Every bit of it should be chosen based on reasoning from first principles.”
                              • “No choice about how to design/build a system is inherently correct or incorrect. Rather, the key question is how suitable each choice is towards the desired outcomes.”

                              I’m just trying to figure out whether I’m getting your point clearly. If not, maybe it would help if you were to provide a fictional example of a conversation with a senior programmer who starts out disputing you, and then is convinced as you talk through examples from their work.

                              1. 2

                                How about (in regards to coding): It is impossible for any line of code to be written unless the programmer is balancing what she wants the code to do against their own set of rules for how things should be coded. The behavior part is explicit and what everybody focuses on. The values/rules part is almost entirely hidden.

                                If we want to write better code, we need to understand how coding happens. From there, we can “drive the train backwards”, taking coding situations where we have poor outcomes and looking at the desired behaviors and values the coders used when creating them.

                                I’ve got a few concepts that this is the foundation for, such as Good Enough Programming, Incremental Strong Typing, and Code Budgets.

                                From there, I’ve got a few examples of fun coding projects that apply them. I’m hoping to get there with these videos. But you gotta start somewhere. If folks don’t understand why code happens, the balancing act that is required, they’ll just get hung up further down the road.

                          1. 2

                            !$work - Continuing a rewrite of the UI for a tactical game I’m working on (https://twitter.com/stratagemstudio). We got feedback that our current UI paradigm is still confusing. Ripping out some smaller features, and reorganizing the ability placement to give players a clearer understanding of what’s going on.

                            1. 1

                              I gotta say, that game looks super interesting from an art standpoint. Do you have a place (other than twitter), where I can sign up to get updates? Perhaps an itch.io page or a place where I could wishlist it on steam?

                              1. 1

                                There’s an Instagram account as well, but it’s usually the same content. You can follow the artist at https://instagram.com/greatseamonster, he’s really great!

                                1. 1

                                  It’s nice to see Godot devs working on cool stuff. I’ve used it some on the side, and it seems to hit a nice spot, at least for smaller projects. I’m still learning a lot of the knobs and how to do certain things. (I just figured out how to work with repeating a sprite this weekend).

                            1. 3

                              Besides the usual stuff, I had a friend on Twitter just now ask if there were any easy html/js chess boards. He wanted to easily be able to represent a position and then talk about moves.

                              I thought this would be a cool little 1-4hr side project to use to talk about coding, but frankly, after poking around a bit, I’m not sure there’s enough problem there to need a solution. The basic solution is almost trivial with the latest web tech and while I could certainly make it more complicated (doing things like taking various forms of notation or scripting piece moves), none of that is what he asked for. So right now I’m leaning towards “no” That sucks. I love both chess and talking about how to come up with solutions for people.

                              So I guess I’m going to look around for something fun to code and share, maybe go ahead and code it out. Don’t know.

                                1. 2

                                  So, why not make make it, if it’s almost trivial?

                                  If you don’t, I may try to pick it up as a small web page.

                                  1. 1

                                    Unless it’s something that the friend can do, if course.

                                    I was mostly thinking of making it easy to copy/paste boards to various fora, but I suspect that they already have chess notation markup that does what they need.

                                    1. 1

                                      Frankly I don’t know where to stop. Board? Almost trivial. Pieces on board? Same. Now what? There are multiple formats to indicate/persist board state, do I capture all of them? Only one? Local database, remote database, or hardcoded js? How about moves, both previous and future (which would involve different coding)

                                      The multiple formats gives me pause, as does the idea of writing a chess-scripting engine (en passant? 50-move rule? Can white castle, etc) Here we get to the point where there’s no one right answer, not even an answer that I would consider robust. I’d code it one way, my friend would want another. People would want to save, perhaps persist games.

                                      Even blowing it all out as far as possible, it doesn’t look like a monster, maybe 1-4 days of part-time coding. It’s got that producty-feel to it, where I make it and then scrounge around looking for folks willing to try/use. Just seems like a headache.

                                      I’m still thinking about it, though. Maybe I’ll just do an initial board setup and see if my friend likes it. That could show off some new tech without getting too far out in imaginary-requirements land.

                                      I’ll decide today.

                                      1. 1

                                        Fair enough, knowing where to stop would be a challenge. For me, my main thought was just a website that server-side renders a board based on a board layout in a URL, and adding a few options to copy/paste that (using JS Canvas for copying images, perhaps). Chess boards as a function, without state. Any more than that, and I’d want to find some sort of return for it, which seems unlikely for such a small thing.

                                        1. 1

                                          You could do a true SPA, something that would run on a thumbdrive. Then the rest of the tech doesn’t matter. Want to deliver json from a server? Cool. Want to deploy with various games and provide a sample pack, no server? Cool. Want to add message queuing or something else and play a million games at a time? Cool. No problem.

                                          In fact, that’s probably how I’d start.

                                  1. 4
                                    1. I finished the website for basho - which lets you to write complex shell tasks using plain JavaScript. It’s at https://bashojs.org

                                    2. Started a company and launching its first product tomorrow. It’s an API gateway written in Node + TypeScript. The website is WIP, but it can still give you an idea https://retransmit.io/

                                    1. 1

                                      Bash looks really cool, I may have to give it a shot.

                                    1. 3

                                      My wife and I have been doing an art challenge, and I’ve been doing a blog post a week on that, so the second post goes up this weekend (the first post went up last week).

                                      My wife’s parents are coming to visit for a few days, so will be spending time with them. Other than that, going to try to catch up on sleep a bit. I’ve been on the edge of not getting enough sleep this week, and it’s starting to catch up to me.

                                      1. 3

                                        Pinging @hwayne, since he’s the author of this.

                                        So, a lot of these tend to follow the sorts of ad-hoc sorts of structures I tend to build using ripgrep or reference following or debugging.

                                        I think this would be best combined with something like that datalog-based IDE, so that one could build these analysis passes on the fly.

                                        Granted, it would be a lot of work to pull off.

                                        1. 5

                                          IMO the ability to make hyperspecialized one-off analysis is 1) incredibly powerful and 2) something we don’t really know how to make accessible to generalist programmers.

                                          1. 1

                                            What tools exist in that space as things are right now, short of writing/modifying a compiler?

                                            For me, code-analysis has either been something baked into a compiler, or something I’ve done by hand, more or less, sometime with mechanical aids, and sometimes not.

                                            1. 1

                                              I suppose the exceptions to that would be things like writing interpreter hooks, or using method_missing type approaches.

                                              1. 1

                                                I wish I knew more about it… almost everybody I know who seems to do this stuff is doing it with regexes and grep.

                                                1. 1

                                                  I could see something akin to XPath working out, if you had the syntax tree in some sort of “regular” form. Of course, that still makes it hard to figure some things out, and what you can pull off depends largely on what has been exposed on the tree in question.

                                          1. 1

                                            I’ve been unknowingly using Emacs Lisp since much earlier – not in the sense of writing packages – my old man taught me how to use Emacs when I was nine

                                            (This makes me jealous)

                                            I decided to scrap my BMP encoder and go with PPM instead. Netpbm is text-based

                                            I was playing around with a NetPPM encoder myself in Scheme, just a few weeks ago, having have read the same article, and storage-wise, it’s helpful to remember that NetPPM can also be generated using binary data. The header stays the same, but after the P6 100 200 256 part, you just write bytes.

                                            Clojure’s license makes it a complete non starter for me, sorry. Live free or die.

                                            What’s this about? I recently read RMS saying that an argument to not consider Clojure a proper lisp is that it’s (allegedly, idk) based on cons-cells, so that “the most basic programming techniques of Lisp don’t work in Clojure”.

                                            1. 6

                                              What’s this about?

                                              EPLv1 isn’t GPL-compatible. Not totally evil, but it’s enough for me to want to avoid using it.


                                              1. 3

                                                Fun facts:

                                                • the EPLv2 is GPL-compatible
                                                • the Clojure developers have collected copyright assignment from all contributors, which would be needed to update the license to use it
                                                • despite this, the Clojure developers have indicated that they are uninterested in doing so
                                                1. 1

                                                  Would it make you feel better or worse if it were MIT?

                                                  1. 2

                                                    If Clojure were licensed under MIT? I would feel better, as it’s compatible with the GPL.

                                                2. 3

                                                  If you’re interested in Clojure, by the way, Phil Hagelberg (who wrote Leiningen, the standard Clojure build tool) is nowadays contributing a lot to Fennel (which is also mentioned in the article, and compiles down to Lua).

                                                  Libre Lounge has a really fascinating interview with him that covers that topic – caveat auditor, I ended up buying his Atreus keyboard after listening to the podcast.

                                                  1. 5

                                                    Careful, for he lurks among us. Some say that if you say the word “technomancy” out loud three times he may appear.

                                                  2. 2

                                                    From what I can see, Clojure uses the Eclipse Public License? (based on https://github.com/clojure/clojure).

                                                    Is the EPL that problematic?

                                                  1. 3

                                                    I’m coding some simple simulations in Ebiten “A dead simple 2D game library for Go”. This means refreshing my vector math knowledge so I’m writing a tiny library too.

                                                    Some people took me up on a free coding mentorship offer so I have some time booked in for that. I’m excited to catch up with all three (maybe four) of them!

                                                    1. 2

                                                      Do you know what the typical solutions for sounds are in Go video games?

                                                      1. 1

                                                        I’m afraid I don’t but maybe someone will chime in 🙂. I’ve only used Ebiten’s audio package which worked for my basic use cases.

                                                        1. 2

                                                          Ah, if they have an audio package, that’s enough of a thing for me. I just didn’t see it at a glance.

                                                    1. 2

                                                      Lots of cleaning, a blog post aggregating the the first week of the art challenge that my wife and I have been doing together. Maybe some Prey, or porting my blog from Go to Elixir, but those are all strictly optional

                                                      1. 19

                                                        Syntax coloring isn’t useless, it is childish, like training wheels or school paste. It is great for a while, and then you might grow up.

                                                        This seems… Overly dismissive? I’ve seen a few programmers talk about working without syntax highlighting, but I know for me, it’s a nice aid for navigating code. It gives my eyes and brain more structural hooks to hang things on, and makes skimming a lot easier, even when it’s all in gray-scale. (Skimming is one of the main ways I read code, looking for the relevant part of a file or function). I will admit that I’ve not been programming as long as Crockford, but I’ve also not been developing for an insignificant amount of time either.

                                                        Plus, pervasive Navigate To Definition for the languages I use, or Vim’s # and * commands help me track down what context a variable comes from pretty easily in most cases.

                                                        1. 5

                                                          Yeah, that part irked me as well.

                                                          I also see his point: common uses of syntax highlighting tend to go overboard. Each piece of syntax we style differently attracts attention. Thus, in a language that leans on parenthesis, rainbow parenthesis are remarkably sane. In another language, coloring every set of parenthesis isn’t as useful.

                                                          I just checked CLion and found a few things that I appreciate that use syntax highlighting:

                                                          • strings as a different color, so I can tell when I miss one
                                                          • macros as a different color
                                                          • unused vars grayed out
                                                          • keywords as a different color

                                                          Not all of them are must have, but it’s a much shorter list than a lot of the popular syntax coloring schemes, which seem to revel in using a different color for each type of syntax it can find. Less really is more.

                                                          1. 2

                                                            Yes, there definitely is a balance in how many different things are syntax highlighted, and one can definitely go overboard. (Right now, I’m used to having types highlighted differently than variables, but it’s not a must).

                                                          2. 5

                                                            The main idea is not bad, but I agree it’s a weird and unnecessary flex. He sounds extremely out-of-touch.

                                                            1. 7

                                                              I thought for years that I needed syntax highlighting, until I gave going without a serious shot. I would never go back to angry fruit salad after a couple years working with it off. Colour can have some uses but syntax highlighting defaults are not the way for me.

                                                              I think a lot of people are where I was: convinced they need the highlighting because it is what they have known.

                                                              1. 6

                                                                I can definitely imagine how you can do without, or even thrive in the absence of, syntax highlighting, and I should experiment with that some time. I’m calling him out of touch for insinuating that something that’s the default for probably 99.99% of programmers is a conscious decision favored by the immature code-illiterate newbs. Gratuitous, because one can simply remove those statements to no detriment to the point.

                                                                1. 4

                                                                  I think the best approach is to come up with your own theme. For example, I’ve been using my own theme (the screenshots are a bit dated) for the last decade or so. Over the years I’ve gradually reduced the amount of colour, leaving colour for elements that I want to stand out. I did try a few greyscale/low-colour themes, but I found it made my eyes more tired than usual.

                                                                  1. 2

                                                                    +1 for making your own theme.

                                                                    It’s been a lot of work and even though I think mine is pretty rudimentary based some others I’ve seen, it’s been really nice.


                                                              2. 4

                                                                It’s something Russ Cox(?) has mentioned too. Maybe it comes from programming before it was widely available. Personally I don’t think it helps you navigate code, because syntax highlighting doesn’t particularly highlight the logic or program flow, it instead helps one navigate text, to form a mental model of where one might find code. But it’s nice to have, at least to stop the screen blurring into a mess if you stare too long, at most to identify where things are happening at a glance as you said.

                                                                1. 1

                                                                  I suppose I don’t see the difference between navigating code, and navigating text? I know that code isn’t just text, but text (or some representation), is the representation of code one usually interacts with. Or rather, the distinction seems small enough as not to matter? In order to navigate code, you must first be able to navigate the text it is comprised of, no?

                                                                  1. 1

                                                                    My beef is that it generally highlights the obvious (keywords) and not so much the less obvious (confusingly similar symbol names, brace matching, assignment over equality, etc.). I would at minimum want comments and strings highlighted though.

                                                                    1. 1

                                                                      I very much want an emacs color theme that does this, but haven’t managed to find one.

                                                                  2. 3

                                                                    The language being used here is certainly not how I would phrase it; It’s almost, ehm, childish :-) But ignoring the choice of language, I do think he has a decent point overall. The quote continues with “I no longer need help in separating operators from numbers. But assistance in finding the functions and their contexts and influences is valuable”

                                                                    In other words: I don’t think Crockford is against this kind of usage of syntax highlighting, just “trivial” syntax highlighting which doesn’t give the advantages you describe (and even proposes a novel way to do highlighting to get similar advantages).

                                                                    This matches my experience; some syntax highlighting I see wants to colour every little thing, which in my opinion is much less useful than colouring useful “anchor points” such as comment blocks, control statements (if, for, return, etc.), and function/class definitions. I also find it slightly useful to highlight strings as I often use that when scanning code as well.

                                                                    Highlighting stuff beyond that like operators, numbers, function names, function calls, highlighting function calls different from method calls, and whatnot: I don’t really see how that’s helpful, and find it even detracts from the ability to scan. It’s some matter of personal taste of course, but syntax highlighting is UX design and like all UX design there’s good designs and bad ones. An interesting and perhaps more striking example of this is this page on colour design in flight control systems.

                                                                    1. 1

                                                                      How about syntax coloring the natural languages? So we give nouns, verbs, adjectives, and etc different colors. All the punctuation marks also get their distinctive color. I would call that childish.

                                                                      Context coloring would be useful for natural languages. So we can immediately see which sentences expand the previous statements, and which sentences start a new argument. But has anybody ever done this? Some people do like to make a whole sentence bold. I guess that’s similar to the concept.

                                                                      Both arguments seem to be stronger for natural languages than code. What about formal logic? Lambda calculus? Brainfuck?

                                                                    1. 9

                                                                      This is a great idea for a post that I’ve wanted to write myself. Leaving aside trees, hash tables, and stacks, I probably used less than one “interesting” data structure/algorithm PER YEAR of programming. Some notable counterexamples are two kinds of reservoir sampling, regular languages/automata, random number generation, some crypto, and some info retrieval algorithms.

                                                                      One thing that sparked it is a obscure but long-running debate over whether dynamic programming interview questions are valid.

                                                                      I don’t think they’re valid. It’s mostly a proxy for “I got a CS degree at a certain school” (which I did, I learned dynamic programming in my algorithms class and never used it again in ~20 years.)

                                                                      I challenge anyone to name ANY piece of open source software that uses dynamic programming. Or to name an example in your own work – open source or not.

                                                                      I’ve tried this in the past and nobody has been able to point to a concrete instance. I think the best I’ve heard is someone heard about a professor who heard about some proprietary software once that used it.

                                                                      Related: algorithms used in real software (although this is certainly not representative, since compiler engineering is a subfield with its own body of knowledge):



                                                                      Linux kernel algorithms:


                                                                      1. 10

                                                                        I challenge anyone to name ANY piece of open source software that uses dynamic programming.

                                                                        Git, or most reasonable implementations of “diff”, will contain an implementation of the Myers Algorithm for longest-common-subsequence, which is very dynamic-programmy.

                                                                        No concrete example for this one, but I know that bioinformatics code is full of dynamic programming algorithms for the task of sequence alignment, which is similar to diff — identifying a way to align two or more base sequences so that they coincide with the minimal number of changes/additions/deletions required to make them identical.

                                                                        1. 1

                                                                          Hm I’m familiar with that algorithm but I never thought of it as dynamic programming.

                                                                          Wikipedia does say it’s an instance of dynamic programming. Although when I click on the paper, it appears to contrast itself with “the basic O(MN) dynamic programming algorithm” (section 4).

                                                                        2. 8

                                                                          Since you mentioned dynamic programming, it’s worth pointing out that the name “dynamic programming” was chosen for political reasons, as pointed out in the history section of the Wikipedia article on dynamic programming. So I think it’s a really bad name.

                                                                          1. 1

                                                                            That’s funny, I remembered xkcd’s “dynamic entropy” comic, and it quotes the same passage:


                                                                            It also has a very interesting property as an adjective, and that is it’s impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible.


                                                                            Agree it’s a terrible name… I would say it was chosen for “marketing” reasons

                                                                          2. 7

                                                                            I have thought about whether dynamic programming questions are fair to ask, and I ended up where you are: they are not.

                                                                            Dynamic programming was the one I struggled most in understanding and implementing correctly. And while there are semi-practical examples (like the backpack problem), I have not found any practical, day-to-day use cases on this.

                                                                            I had an argument with my colleague who asked this kind of problem, saying it’s basic knowledge. Turns out he did competitive programming and there, it is table stakes. But in practice, it just filtered for anyone who has learned and practiced this approach.

                                                                            I stay away from asking this, problems that need dynamic programming to solve.

                                                                            1. 4

                                                                              I’m familiar with dynamic programming mostly from high-school competitive programming as well. Otherwise I can’t say I’ve encountered real-life problems where it occurred to me to use the technique.

                                                                            2. 8

                                                                              I challenge anyone to name ANY piece of open source software that uses dynamic programming. Or to name an example in your own work – open source or not.

                                                                              I’m literally about to implement something that could be classified as dynamic programming at work, which can be sumarrized as “computing a few simple statistics such as number of bytes changed for each directory in a large filesystem”. Dynamic programming is such a general term that it applies regularly if you want to use it.

                                                                              1. 4

                                                                                I’d like to see it. I don’t think dynamic programming is a general term.

                                                                                In fact one time I participated in this argument (which was years ago so my memory is fuzzy), a former CS professor I worked with explained the difference between memoization and dynamic programming. A bunch of 10-20+ year programmers like myself went “ah OK”. Unfortunately I don’t even remember the difference, but the point is that most programmers don’t, because dynamic programming is very uncommon.

                                                                                What you’re describing sounds like an obvious algorithm that anyone could implement, which is not the same as dynamic programming interview questions, or dynamic programming in competitive programing.

                                                                                As other posters mentioned, competitive programming is the main place you see it outside of a CS class.

                                                                                1. 2

                                                                                  It’s absolutely an obvious algorithm, so is most dynamic programming. That was sort of my point.

                                                                                  Can’t share the code unfortunately, but it’s just iterate over sorted list of file changes in reverse order and collect statistics as we go. Dynamic part comes from the fact that we can just look at the subdirectories of a dir (that we already have numbers for) instead of recursing into it.

                                                                                  1. 2

                                                                                    What you’re talking about could be called memoization, or it probably doesn’t even deserve that name. It’s just what a “normal” programmer would come up with.

                                                                                    That’s not the type of thing that’s asked in interview questions or competitive programming. The wikipedia page gives some examples.

                                                                                    Dynamic programming usually changes the computational complexity of an algorithm in some non-obvious way. There’s very little you can do recursing over a directory tree that doesn’t have a clear O(n) way to code it (e.g. computing statistics).

                                                                                    1. 7

                                                                                      I like Erik Demaine’s explanation, that problems where dynamic programming can be applied are ones where their subproblems and their dependencies can be modeled as a directed acyclic graph [1]. Up to you if you’d like to tackle that with a top down approach where you look at a node and calculate its solution based on the solutions of its ancestors, or a bottom up approach starting from the nodes in the DAG with no dependencies and propagate the solutions in topological order.

                                                                                      My colleague and I used it for a generalization of matrix chain multiplication (for tensors) [2].

                                                                                      [1] https://youtu.be/OQ5jsbhAv_M?t=2736

                                                                                      [2] https://github.com/TensorCon/ratcon/blob/release/opt/gencon/pathopt.py#L198

                                                                                      edit: by the definition above, even naive memoization can count as DP, if you’re caching solutions to subproblems of that structure. Doesn’t have to be at the difficulty level of competition to count as DP in that case.

                                                                                      1. 1

                                                                                        Hm interesting, searching through my personal wiki, I found a related definition which is different. I haven’t really thought about it enough to form an opinion.

                                                                                        Either way, it doesn’t change my overall point: that there are certain kinds of algorithms problems that appear on coding interviews, and in competititve programming, that do not show up in 99% of programming jobs. They are easy to pose and have cute solutions, but aren’t testing very much.

                                                                                        I think the “DP tables” part is key but again I haven’t thought about it enough …


                                                                                        Memoization is fundamentally a top-down computation and DP is fundamentally bottom-up. In memoization, we observe that a computational tree can actually be represented as a computational DAG

                                                                                        In DP, we make the same observation, but construct the DAG from the bottom-up. That means we have to rewrite the computation to express the delta from each computational tree/DAG node to its parents. We also need a means for addressing/naming those parents (which we did not need in the top-down case, since this was implicit in the recursive call stack). This leads to inventions like DP tables, but people often fail to understand why they exist: it’s primarily as a naming mechanism (and while we’re at it, why not make it efficient to find a named element, ergo arrays and matrices).

                                                                                        This bottom-up / top-down distinction might have been the same as what the aforementioned professor said 5+ years ago, but I don’t remember exactly.

                                                                                        1. 1

                                                                                          So, is memorization of factorial top-down, or bottom-up?

                                                                                          1. 1

                                                                                            I would probably say neither… Either factorial or Fibonacci is so trivial that it doesn’t help to be thinking about it that way.

                                                                                            Though I think the quote hints at a clear test for whether it’s top-down or bottom-up: if you need extra state outside the call stack. I’m getting curious enough to try this out, but right now all I can do is quote what other people say.

                                                                                            In any case it’s clear to me that there’s some controversy over what dynamic programming really is. I think the issue is that a lot of algorithms could be framed that way but were not discovered that way, and not taught and learned that way.

                                                                                            1. 1

                                                                                              I would probably say neither… Either factorial or Fibonacci is so trivial that it doesn’t help to be thinking about it that way.

                                                                                              I think that the triviality is actually helpful here. If it’s actually true that memoization and dynamic programming are different (and there’s clearly debate on this), can 2 implementations of a trivial function, that everyone can understand highlight the differences?

                                                                                      2. 1

                                                                                        On the contrary the stupidly naive way (recurse on every directory) is O(n^2).

                                                                                        Dynamic programming is just solving a series of problems while using the answers of shared subproblems multiple times. Memoization is a common way to implement this.

                                                                                        Yes there are some very clever algorithms that use dynamic programming, this doesn’t make obvious algorithms that use dynamic programming not also fit under the definition.

                                                                                        1. 3

                                                                                          Why would recursing into every directory be O(n^2)? You’re still only visiting every directory/file once? It seems like something missing?

                                                                                          1. 1

                                                                                            Say you have a directory structure with a single file in it, /a/b/c/d/e

                                                                                            To get the number of bytes changed in e you need to visit e, then to get the number of bytes changed in d you need to visit d and then e, then for c you need to visit c, d, and e, and so on.

                                                                                            Like I said, it takes a really naive solution, but if you don’t remember the values you calculate anywhere for some reason it’s sum over inodes (depth of inode)… which is O(n^2) (for bad directory structures).

                                                                                            Note that I need these values for every directory, not just for one particular directory.

                                                                                            1. 2

                                                                                              That’s still linear complexity space. Unless you’re hardlinking directories (which you then have to deal with potential recursion), it’s still O(n). If you add a file at /a/b/c/file you only visit 1 more file and no more dirs, not an exponential. O(n + n + n) or O(n + 3) still simplifies to O(n).

                                                                                              1. 1

                                                                                                If you add /a/b/c/file you add 4 more visits, not 1. Going from n= 3 /a/b/file to n=4 /a/b/c/file adds 4 more visits. In other words this worst case example takes time O(sum from 1 to n of i) = O(n(n-1)) = O(n^2).

                                                                                                N is the number of inodes in a arbitrary tree not a number of files in a fixed tree.

                                                                                                1. 1

                                                                                                  That’s still adding a linear number of operations for each file, the depth could technically be considered a different variable, say m. So for each file (n+1) you add, you also add the number of directory traversals (m) resulting in O(m+n), which simplifies again to O(n), but in reality folders are files too, so are part of n in the first place, so again O(n). Ultimately your n space is the total number of inodes, which both files and folders have.

                                                                                                  Abstractly, you’re just traversing a tree structure (or a directed graph if using links), which is well understood to be O(n) (maybe O(n^2) worst case if all folders are links, resulting in a fully connected graph), because you only visit each node once. If it were O(n^2), you would visit each node n times.

                                                                                                  Remember, Big O notation is about scaling, not the actual concrete number of operations, which is why you drop any constants or variables other than n.

                                                                                                  1. 1

                                                                                                    It’s O(mn) not O(m+n) (in the insanely naive algorithm that recalculate things every time).

                                                                                                    It’s not a single tree traversal but #internal nodes tree traversals.

                                                                                                    1. 1

                                                                                                      Even if it was O(mn) (it’s not), that still simplifies to O(n). An ‘internal nodes’ tree traversal is still O(n), n is just smaller, but again, your problem is not an internal nodes traversal, it’s a full traversal because you have to look at the blocks attached to the file (leaf) inodes, which means you need to read all inodes of all files and of all folders one time each. n = # of files + # of folders = O(n)

                                                                                                      1. 1

                                                                                                        I supposed an extremely naive solution could be to fully traverse each sub tree for every folder visited, which would be… O(log n)? But even that isn’t O(n^2), as the total repeated space shrinks the deeper you get.

                                                                                                        1. 1

                                                                                                          You’re assuming a balanced tree, which is not guaranteed. Depth of tree is O(n) in pathological cases (and average case O(sqrt(n)) is typical for randomly generated trees)

                                                                                                          1. 1

                                                                                                            Ah yeah, I think it would be O(n log n) not O(log n), because you traverse the tree once for each node, and a subset of of the tree for almost every n (except leafs), at least in the worst case. Still not O(n^2), and the solution for a O(n) is almost easier to conceptualize than the completely naive solution :)

                                                                                                            1. 1

                                                                                                              and the solution for a O(n) is almost easier to conceptualize than the completely naive solution :)

                                                                                                              No argument here…

                                                                                                              I think it would be O(n log n)

                                                                                                              We agree it’s O(n) * O(time tree search) now right? And you’re trying to call the tree search time log(n)? Because trees are height log(n)? Then see the post you replied to, that’s true in a balanced tree, it’s not true in a random tree (where it is sqrt(n)) and it’s definitely not tree in a pathological worst case (where a tree is just a n length linked list).

                                                                                                              1. 2

                                                                                                                Yeah, the part I was hung up on before was that you’re naive solution traverses the entire subtree below a node for each node visit, I was stuck in the simple optimal solution. For the pathological case, basically just a bunch of folders in folders with a single file at the bottom, the depth of the tree is n, and the file inode at the bottom would be accessed n times, so O(n^2). For the common case it would be about O(n log n) where you can skip traversing larger and larger parts of the tree the deeper you get on each ‘path.’ Thanks for the discussion, I enjoyed it :)

                                                                                      3. 1

                                                                                        I think comparing memoization to dynamic programming is a category mistake: they are different kinds of things.

                                                                                        ‘Dynamic programming’ is a description of a style of algorithm. It’s divide-and-conquer, usually with overlapping subproblems, making it possible to reuse intermediate results.

                                                                                        Memoization is a programming technique to remember intermediate results, by remembering the results of function calls. You can e.g. also store the intermediate results somewhere explicitly, usually in a matrix, in which case you don’t memoize the result ‘transparently inside the function’, but use a lookup table ‘external to the function that computed the result’.

                                                                                        1. 1

                                                                                          I dunno I find that in addition to the Racket language resource I gave elsewhere in the thread, lots of people compare them:


                                                                                          A note on terminology: Some people call top-down dynamic programming “memoization” and only use “dynamic programming” to refer to bottom-up work. We do not make such a distinction here. We call both dynamic programming.

                                                                                          There does seem to be disagreement on what dynamic programming is. And many algorithms that were not derived with dynamic programming techniques could be described as dynamic programming.

                                                                                          But it seems that most people agree it’s related to memoization.

                                                                                    2. 4

                                                                                      GCC uses dynamic programming to split IA-64 instructions into bundles.

                                                                                      1. 2

                                                                                        Thanks, nice example and link! Still I would say it’s a niche skill, especially to come up with from scratch in an interview.

                                                                                      2. 4

                                                                                        I challenge anyone to name ANY piece of open source software that uses dynamic programming. Or to name an example in your own work – open source or not.

                                                                                        Ever do video encoding or transcoding with anything built on FFmpeg or x264? Encode images with MozJPEG? Encode an AV1 video or AVIF image with libaom? Trellis quantization in advanced lossy compression encoders is a dynamic programming algorithm.

                                                                                        1. 3

                                                                                          Hm very interesting! I was not aware of that algorithm. Paper I found:


                                                                                          I would still say it’s a bad interview topic, but it’s cool to see real world usages of it.

                                                                                          1. 2

                                                                                            Oh, no disagreement there! Even after coding it up myself, I’d hate to have someone ask me to whiteboard a working implementation of trellis quantization in 40 minutes or whatever (though I’m pretty sure I could sketch out an explanation now).

                                                                                            In general I’m not a fan of whiteboard coding exercises at all. Whenever I’ve interviewed candidates I’ve always preferred the old-fashioned method of just reading their resume well ahead of time, looking up what ever piques my interest on it, and then having a friendly conversation about that. Usually that provides plenty of esoteric material for me to quiz them on and it also lets them show me their strengths and enthusiasm.

                                                                                            1. 1

                                                                                              My current company doesn’t do a whiteboard exercise, but my previous one did… but the thing is, the usual task was to implement a basic “grep”. That is, read a file and print all of the lines that contain a user-specified string, in a language of your choice, with whatever libraries make you happy (it’s not a trick, you’re not supposed to implement Boyer-Moore on your own). Assuming you succeeded at that, we would ask you to implement a few more features, like a -v flag (only print lines that don’t match), and -A and -B flags (print context lines before and after the matching line), until you got stuck or the time for that segment was up. It wasn’t graded on minutiae like correct semicolon placement, it was just an evaluation of whether a candidate could do a trivial task, how they handled additional requirements, whether they asked sensible questions and got clarification when needed, etc. I found it pretty reasonable.

                                                                                        2. 4

                                                                                          I challenge anyone to name ANY piece of open source software that uses dynamic programming. Or to name an example in your own work – open source or not.

                                                                                          I used Warshall’s algorithm (which is dynamic programming) to compute the transitive closure of a graph for a typechecker. This is, in my experience, a very common algorithm.

                                                                                          In high school, I wrote a program for my professor that places students into groups of 4 such that their meyers-briggs personalities are as different as possible. This used dynamic programming.

                                                                                          A professor of mine (who taught the subject to me) used dynamic programming for some kind of RNA sequencing problem in a paper he published. One of our homework assignments had us arrive at a watered down version of his (and his co-authors’) algorithm.

                                                                                          I’m fairly certain that at least some fuzzy string matching algorithms use string distance, which is also solved using dynamic programming.

                                                                                          These are all diverse applications of DP. In my personal, subjective experience, the idea that DP is in any way obscure or dated is absurd.


                                                                                          To be more concrete, the “transitive closure of a graph” is for the graph of dependencies, computing the set of all functions that a particular function depends on. This is as described in the Haskell Report.

                                                                                          For fuzzy string matching, I have in mind something like fzf, though I cannot say with certainty that it uses string distance (I’m unfamiliar with its implementation).

                                                                                          Here’s the paper that I think I’m referencing: Statistical Mechanics of Helix Bundles using a Dynamic Programming Approach

                                                                                          1. 2

                                                                                            Thanks for the examples. The claim is definitely not that it’s outdated or obscure; the claim is that it’s not a good interview question because it doesn’t show up much at work. Although there were lots of people here who pointed out interesting uses of dynamic programming, that’s not incompatible with the idea that you could have a 10 or 20 year programming career and never use it.

                                                                                            Side note: I’m familiar with the Floyd Warshall algorithm but I never thought of it as dynamic programming. I think part of the issue is that I may have a more narrow definition of it than others. (I think people even say the linear time fibonacci is an example of dynamic programming, which I find silly. I just call that the obvious algorithm. I guess it can be used to illustrate a principle.)

                                                                                            Even so, I definitely think it’s more popular in universities, and certain domains like bioinformatics. In contrast to what people on this site typically do “for work”.

                                                                                          2. 3

                                                                                            I challenge anyone to name ANY piece of open source software that uses dynamic programming. Or to name an example in your own work – open source or not.

                                                                                            I do a lot of work with text processing – computing the edit distance between two strings is something I do very often. That’s a classic dynamic programming algorithm. There are probably hundreds of open source packages that do this or some variation thereof.

                                                                                            1. 3

                                                                                              Just to add to the list of responses clearly demonstrating Cunningham’s Law:

                                                                                              I believe the Knuth-Plass line-breaking algorithm used in LaTeX to lay out text “optimally” uses dynamic programming. This was done for efficiency, as opposed to using some kind of general global optimization routine. It’s also the reason why LaTeX doesn’t support “backtracking”.

                                                                                              1. 2

                                                                                                It’s also the reason why LaTeX doesn’t support “backtracking”.

                                                                                                Sile uses a variant of the same dynamic programming algorithm to lay out paragraphs on a page. The original paper describing the algorithm says that TeX wanted to use it like that, but it would require more than one entire megabyte of state for a large document, which was infeasible.

                                                                                                1. 1

                                                                                                  Definitely an instance of Cunningham’s law at work :) I should make another go for my pet problems:

                                                                                                  • it’s impossible to make a zsh-like interactive interface on top of GNU readline
                                                                                                  • you can’t make a constant-space linear-time model of computation that’s more powerful than regular languages, and that can parse shell/JS/Python/C++
                                                                                                  • you can’t make an extended glob to regex translator in less than a week (https://github.com/oilshell/oil/issues/192)

                                                                                                  Thanks for the example. If there were more specific links I would make a blog post out of this :)

                                                                                                  And although my comment was a tangent, it did motivate me to get out the “Algorithm Design Manual” and flip to the part on dynamic programming. Though I remember the applications in that book being interesting but seemingly far removed from what programmers do day-to-day. It seemed to be by a professor who consulted on algorithms for various companies, which is an interesting job!

                                                                                                2. 1

                                                                                                  The Grasshopper routing library uses contraction hierarchies, which are implemented using Dijkstra’s shortest path algorithm and A* search, which are special cases of dynamic programming.

                                                                                                  I have to agree it’s not something most people will use every day, but it never hurts to have a general idea how it works.

                                                                                                  1. 1

                                                                                                    Here is a concrete example of Dynamic Programming that you use every day: Word Wrap. Knuth has an algorithm that is often used for maximizing the number of words per line.

                                                                                                    Also the field of Bioinformatics often uses the Levenshtein distance when matching two dna strands.

                                                                                                    Also I would like to mention the single most important thing I learned from Dynamic Progrmming: Start at the end case, and figure out what constraints can work from there. For example, think about the last recursion call, and what constraints it needs, and go backwards from there.

                                                                                                  1. 4

                                                                                                    What’s interesting for me, is that I don’t find that coding and (jigsaw) puzzles hit the same parts of my brain at all.

                                                                                                    Or rather, I have enough experience, I usually can get a handle on coding. Puzzles, on the other hand, seem to frustrate me a lot more easily.

                                                                                                    Not to say the analogies are incorrect, but I was surprised when I actually tried jigsaw puzzles a few years ago how much they made my head hurt.

                                                                                                    1. 2

                                                                                                      I just finished the 2020 GMTK Game Jam with a friend, so I’ll be rating other submissions over the week.

                                                                                                      My wife and I are doing an art challenge together, which is a good excuse to practice my pixel art. Other than that and work, I plan on taking things slower this week.

                                                                                                      1. 1

                                                                                                        Very cool! Do you have any prior experience with pixel art? I find it a bit daunting.

                                                                                                        1. 1

                                                                                                          I do. I’ve made a few game jam games with it, and have used it off and on over the years. In fact, my Lobster’s avatar is my own work.

                                                                                                          If you’re going to get into it, a few small tips are to think of it more like sculpting than drawing, and to start with some reference imagery, if you’re trying to draw something from real life. Also, I typically use 16x16 or 32x32 sprites as a starting point. Also, doing a bit of googling on how to do it can help, there’s some good resources on how to do it. The biggest thing you need to do is shed the idea of everything having a black outline, at least at low resolutions.

                                                                                                          If you’re going to get into Pixel Animation, I recommend picking up Asperite (or a program like it, I’ve also used Pyxel edit, but I like Aspterite better). Having a dedicated program for testing your animations is handy, and will save you turn-around time.

                                                                                                          1. 1

                                                                                                            Thanks for the tips! The idea of sculpting vs drawing is especially helpful.

                                                                                                      1. 1

                                                                                                        That is both a practical and cute bit of shell metaprogramming. I am also guilty of using sed in a bit of shell metaprogramming, for some directory bookmarks.