Comments (16)
from astar-gridmap-2d.
Optimizer flags are cheap tricks. No one can optimize my code, no one! I am the only one able to do it, buahahaha
(laughing maniacally)
But of course you can stop using A* and use something else ;)
from astar-gridmap-2d.
I'm happy to admit that the code is nice as it is, so there isn't much room for optimization :)
The optimizer flags seem to make a big difference though
from astar-gridmap-2d.
Hi Francois:
I just run the code again by setting the compiler flags that suggested, it really improves the performance a lot, please check the following results.
- Before optimization:
$ ./build/benchmark
2019-10-05 07:45:41
Running ./build/benchmark
Run on (8 X 3800 MHz CPU s)
CPU Caches:
L1 Data 32K (x4)
L1 Instruction 32K (x4)
L2 Unified 256K (x4)
L3 Unified 8192K (x1)
Load Average: 0.04, 0.07, 0.14
Benchmark Time CPU Iterations
BM_AStar_Big 1911860219 ns 1909029534 ns 1
BM_AStar_Smooth_1000 1363989087 ns 1361915866 ns 1
BM_AStar_Small 5070272 ns 5063018 ns 133
- After optimization:
BM_AStar_Big 175500144 ns 175166215 ns 4
BM_AStar_Smooth_1000 123446411 ns 123190568 ns 6
BM_AStar_Small 382802 ns 382080 ns 1899
And in fact, I am writing my solution for the shortest path problem, pls check the following results:
-
Before optimization:
BM_LS_Big 458208892 ns 457507908 ns 2
BM_LS_Smooth_1000 45481337 ns 45399325 ns 16
BM_LS_Small 2159268 ns 2153314 ns 330 -
After optimization
BM_LS_Big 27097026 ns 26997710 ns 24
BM_LS_Smooth_1000 5558547 ns 5520143 ns 115
BM_LS_Small 192361 ns 191769 ns 3632
All the above tests are using the same image file.
Would you pls let me know where I can download some more files for testing, I tried google for the image files, some can run, while some can't. Interestingly, when it fails to run, both your code & mine are also failed.
Regards
Patrick
from astar-gridmap-2d.
Hi Francois:
One thing forget to mention, my solution doesn't using the A* approach.
Regards
Patrick
from astar-gridmap-2d.
Tiny optimization here (15%), using the power of the CPU branch prediction instead of one level of indirection.
from astar-gridmap-2d.
Hi Francois & Davide:
I just found there is a competition about grid based path planning almost every year, different algorithms are used, details can be found from the website www.movingai.com, and results of 2014 can be from from the following URL:
https://www.cs.du.edu/~sturtevant/papers/GPPC-2014.pdf
Codes can be found from the following URLs:
https://github.com/maxrenke/gppc-2014.git
https://github.com/nathansttt/hog2.git
I am integrating my algorithm to see the difference.
Regards
Patrick
from astar-gridmap-2d.
There is no way this vanilla A* can compare with those algorithms. It is not the purpose of this repository
from astar-gridmap-2d.
Hi Davide:
I totally understand that.
I am working for robot vacuum cleaner project, which using the STM32F0x series CPU, so I have to make sure my algorithm as effective as possible, that is why I am looking for some 3rd party's resources to compare with mine. Your repository is really great to me already, and I really appreciate for your works.
Regards
Patrick
from astar-gridmap-2d.
You probably need something MUCH more efficient than this, both in terms of memory usage (we use a lot of RAM) and CPU.
I think you will eventually need something based on Jump Point Search (JPS). Anyway, I am happy if you find this useful. Let me know if you eventually compare the results of this implementation with GPPC-2014, I am curious :)
from astar-gridmap-2d.
Hi Davide:
Yes, you are right, the memory usage is another constrain.
I sent an email to Prof. Nathan and got the reply from him, he said he would provide a shell script to me which could generate the test result, I am waiting for that.
For what I tested so far, it looks like my algorithm is almost as efficient as BLJPS, but still much to optimize while compare will NSubgoal.
After I have the script from Prof. Nathan and have the results, I will let you know.
Regards
Patrick
from astar-gridmap-2d.
would you share your code? I will be happy to help you optimizing it
from astar-gridmap-2d.
Hi Davide:
Sure, after I receive the shell script from Prof. Nanthan, and have the preliminary test result.
Regards
Patrick
from astar-gridmap-2d.
Now that I read more about JPS algorithm, I think I will implement it for fun in a new repository.
There is no way A* can compete and the fact that the path has less nodes is nice.
from astar-gridmap-2d.
Wah, maybe you will be one of the participant of the coming GPPC event. Where to find your repository, shared already? I think it is also worth to take a look at NSubgoal.
from astar-gridmap-2d.
Since I am doing this for fun only, I guess I will focus on my own JPS++ only ;)
I have found this https://github.com/KumarRobotics/jps3d
It is "only" twice as fast compared with my A* implementation, therefore I am pretty sure it can be optimized even further.
Once I start working on this, I will let you know.
For the record, I am not interested (personally) to any implementation that require a lot of pre-computing for each map.
from astar-gridmap-2d.
Related Issues (5)
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from astar-gridmap-2d.