A* search: optimized implementation in Lisp

> 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.

Re: A* search: optimized implementation in Lisp

#8

Post by 1xtrm0 » Sat, Aug 03, 2024, 1:36 PM UTC

diggan wrote: post #7

efilife wrote: post #4

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

> 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 c…

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

Re: A* search: optimized implementation in Lisp

#9

Post by diggan » Sat, Aug 03, 2024, 2:03 PM UTC

1xtrm0 wrote: post #8

diggan wrote: post #7

Earlier quoted context omitted.

> 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 c…

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…

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?

Re: A* search: optimized implementation in Lisp

#10

Post by mtlmtlmtlmtl » Sat, Aug 03, 2024, 2:20 PM UTC

1xtrm0 wrote: post #8

diggan wrote: post #7

Earlier quoted context omitted.

> 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 c…

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…

>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.