4 ms·

Can someone explain why is this special? It doesn't look anything more than an algorithm implementation

diggan 2y ago
> The library is optimized for SBCL > This implementation of A* running on SBCL outperforms even C++ implementations, at least the ones for which I was able to find performance numbers (1, 2). You can have a look at impressively sleek assembly produced by SBCL for FIND-PATH function here. Beating similar C++ implementations in performance seems at least a bit noteworthy, as C/C++ is often held as the language(s) to chose for best performance.
- 1xtrm0 2y ago
  The "c++ implementations" are two stack overflow answers. I don't think the comparisons are representative of the performance of implementing A*: 1 - Is an innefficient and obfuscated BFS. It has no heuristics. (The lisp benchmark is using Manhattan distance. You can think of it as comparing walking blindfolded on a maze vs having a GPS that tells you how far you are from the exit) 2 - Is a person claiming numbers on a specific instance of a problem that was tested, without showing any code or details on what heuristics were used
  - diggan 2y ago
    I guess the proof is in the pudding. What C++ implementations (with any benchmark figures published) you know about that would beat the one in this submission?
  - mtlmtlmtlmtl 2y ago
    >the implementations are two stack overflow answers. This is pretty uncharitable. One of the "answers" is just a link to the authors research paper. Not like it's just something they quickly threw together for some SO post. It is a bit strange that they link to the SO post and not the paper though.
    - giancarlostoro 2y ago
      But also, a ton of people use SO code verbatim.
      - rowanG077 2y ago
        Do they? I very much doubt that.
        giancarlostoro 2y ago
        For several years I have seen this being the case especially for algorithms people need to use, or regexes.
        klyrs 2y ago
        I can't tell you how many times I've caught juniors trying to pass off unmodified SO answers as their own work. It's rather alarming to me because they have this attitude that popular things can't be wrong, and public things don't need attribution. But knowing, that people often approach life in this way, is half the battle.
        giancarlostoro 2y ago
        Could be worse when I’m really tired I copy the code from the question and fix that.
        hnfong 2y ago
        Lesser known is that SO content is generally under a CC-BY-SA license, which means not only attribution, but also "share-alike", which generally means releasing derivative work under the same license... There is significant legal risk if your juniors are pasting non-trivial code from SO into your codebase verbatim...
whartung 2y ago
It’s also notable that the core algorithm is not a function, but a macro. That means that you end up with an exact representation of the algorithm to the constraints as defined, instead of a general purpose algorithm with parameters. I imagine this could be done with C++ templates as well, I’ve just never used them myself. But this gives the compiler ample opportunities to optimize, since the code is specific to the desired domain. It also hides a bunch of the clutter that typically accompanies optimized Common Lisp code with all of the declares, declaims, and type specifiers.
- pjmlp 2y ago
  With modern C++, it would be a mix of templates, constexpr, constinit and consteval. However I am also on for some Lisp love.
ahoka 2y ago
I was curious too, so I have ran the included benchmark for a 500x500 matrix and my naive Kotlin A* implementation runs faster on the same input. So what are we missing here?

> The library is optimized for SBCL > This implementation of A* running on SBCL outperforms even C++ implementations, at least the ones for which I was able to find performance numbers (1, 2). You can have a look at impressively sleek assembly produced by SBCL for FIND-PATH function here. Beating similar C++ implementations in performance seems at least a bit noteworthy, as C/C++ is often held as the language(s) to chose for best performance.

1xtrm0 2y ago
The "c++ implementations" are two stack overflow answers. I don't think the comparisons are representative of the performance of implementing A*: 1 - Is an innefficient and obfuscated BFS. It has no heuristics. (The lisp benchmark is using Manhattan distance. You can think of it as comparing walking blindfolded on a maze vs having a GPS that tells you how far you are from the exit) 2 - Is a person claiming numbers on a specific instance of a problem that was tested, without showing any code or details on what heuristics were used
- diggan 2y ago
  I guess the proof is in the pudding. What C++ implementations (with any benchmark figures published) you know about that would beat the one in this submission?
- mtlmtlmtlmtl 2y ago
  >the implementations are two stack overflow answers. This is pretty uncharitable. One of the "answers" is just a link to the authors research paper. Not like it's just something they quickly threw together for some SO post. It is a bit strange that they link to the SO post and not the paper though.
  - giancarlostoro 2y ago
    But also, a ton of people use SO code verbatim.
    - rowanG077 2y ago
      Do they? I very much doubt that.
      - giancarlostoro 2y ago
        For several years I have seen this being the case especially for algorithms people need to use, or regexes.
      - klyrs 2y ago
        I can't tell you how many times I've caught juniors trying to pass off unmodified SO answers as their own work. It's rather alarming to me because they have this attitude that popular things can't be wrong, and public things don't need attribution. But knowing, that people often approach life in this way, is half the battle.
        giancarlostoro 2y ago
        Could be worse when I’m really tired I copy the code from the question and fix that.
        hnfong 2y ago
        Lesser known is that SO content is generally under a CC-BY-SA license, which means not only attribution, but also "share-alike", which generally means releasing derivative work under the same license... There is significant legal risk if your juniors are pasting non-trivial code from SO into your codebase verbatim...

whartung 2y ago

It’s also notable that the core algorithm is not a function, but a macro. That means that you end up with an exact representation of the algorithm to the constraints as defined, instead of a general purpose algorithm with parameters. I imagine this could be done with C++ templates as well, I’ve just never used them myself. But this gives the compiler ample opportunities to optimize, since the code is specific to the desired domain. It also hides a bunch of the clutter that typically accompanies optimized Common Lisp code with all of the declares, declaims, and type specifiers.

pjmlp 2y ago
With modern C++, it would be a mix of templates, constexpr, constinit and consteval. However I am also on for some Lisp love.

ahoka 2y ago

I was curious too, so I have ran the included benchmark for a 500x500 matrix and my naive Kotlin A* implementation runs faster on the same input. So what are we missing here?