Giter Site home page Giter Site logo

Code optimization about astar-gridmap-2d HOT 16 CLOSED

eurecat avatar eurecat commented on June 19, 2024
Code optimization

from astar-gridmap-2d.

Comments (16)

chataign avatar chataign commented on June 19, 2024

from astar-gridmap-2d.

facontidavide avatar facontidavide commented on June 19, 2024

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)

image

But of course you can stop using A* and use something else ;)

from astar-gridmap-2d.

chataign avatar chataign commented on June 19, 2024

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.

chaupc avatar chaupc commented on June 19, 2024

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.

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

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

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

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

chaupc avatar chaupc commented on June 19, 2024

Hi Francois:

One thing forget to mention, my solution doesn't using the A* approach.

Regards
Patrick

from astar-gridmap-2d.

facontidavide avatar facontidavide commented on June 19, 2024

Tiny optimization here (15%), using the power of the CPU branch prediction instead of one level of indirection.

#7

from astar-gridmap-2d.

chaupc avatar chaupc commented on June 19, 2024

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.

facontidavide avatar facontidavide commented on June 19, 2024

There is no way this vanilla A* can compare with those algorithms. It is not the purpose of this repository

from astar-gridmap-2d.

chaupc avatar chaupc commented on June 19, 2024

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.

facontidavide avatar facontidavide commented on June 19, 2024

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.

chaupc avatar chaupc commented on June 19, 2024

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.

facontidavide avatar facontidavide commented on June 19, 2024

would you share your code? I will be happy to help you optimizing it

from astar-gridmap-2d.

chaupc avatar chaupc commented on June 19, 2024

Hi Davide:

Sure, after I receive the shell script from Prof. Nanthan, and have the preliminary test result.

Regards
Patrick

from astar-gridmap-2d.

facontidavide avatar facontidavide commented on June 19, 2024

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.

chaupc avatar chaupc commented on June 19, 2024

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.

facontidavide avatar facontidavide commented on June 19, 2024

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 photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo 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.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.