ShortestPath memory improvement

[rschio]

Hi Korthaj, when i was using the ShortestPath function i noticed that it was using a significant amount of memory (I was processing a large graph). It seems that the closure is allocated (or a pointer to it) at each iteration of the loop which makes the function use more memory.

name             old time/op    new time/op    delta
ShortestPaths-8     154µs ± 0%      85µs ± 0%  -45.02%

name             old alloc/op   new alloc/op   delta
ShortestPaths-8    81.0kB ± 0%    41.1kB ± 0%  -49.26%

name             old allocs/op  new allocs/op  delta
ShortestPaths-8       849 ± 0%        17 ± 0%  -98.00%

This package and your blog are awsome.

-Rodrigo

[korthaj]

Thanks for the patch! I really appreciate it. Unfortunately, I'm really busy right now but I will take a look in a month or so. Also, the ShorthestPath function traverses the whole graph, even when not needed. I've been meaning to fix this for a long time. :)

Best regards,

Stefan

On Sun, Sep 13, 2020 at 8:40 AM Rodrigo Schio [email protected] wrote:

Hi Korthaj, when i was using the ShortestPath function i noticed that it was using a significant amount of memory (I was processing a large graph). It seems that the closure is allocated (or a pointer to it) at each iteration of the loop which makes the function use more memory.

name old time/op new time/op delta

ShortestPaths-8 154µs ± 0% 85µs ± 0% -45.02%

name old alloc/op new alloc/op delta

ShortestPaths-8 81.0kB ± 0% 41.1kB ± 0% -49.26%

name old allocs/op new allocs/op delta

ShortestPaths-8 849 ± 0% 17 ± 0% -98.00%

This package and your blog are awsome.

-Rodrigo

You can view, comment on, or merge this pull request online at:

https://github.com/yourbasic/graph/pull/8 Commit Summary

• memory improvement

File Changes

• M path.go https://github.com/yourbasic/graph/pull/8/files#diff-167fa3abc5af405dd53a00a09a35b800 (43)

Patch Links:

• https://github.com/yourbasic/graph/pull/8.patch
• https://github.com/yourbasic/graph/pull/8.diff

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/yourbasic/graph/pull/8, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACVN3S3WZD6TE3QQQGEC7KTSFRSNNANCNFSM4RKPLHCA .

[rschio]

No problem, thank you.

[marco-m]

Hello @korthaj, would you have time now to look at this PR? It looks promising. As @rschio, I do enjoy your blog and this module :-) thanks!

[korthaj]

Yeah, it's about time. It seems I'm a few years behind. In fact, I just updated my Go version from 1.12 to 1.16...

Thanks a lot @rschio https://github.com/rschio. It really is a nice patch with huge improvements to both time and memory. In a perfect world, the compiler and runtime would do this automatically. But since it hasn't happened yet, it probably never will. I suspect there are several other algorithms in this package where a similar optimization would help. I'll take a look.

On Sat, Jun 5, 2021 at 1:53 PM Marco Molteni @.***> wrote:

Hello @korthaj https://github.com/korthaj, would you have time now to look at this PR? It looks promising. As @rschio https://github.com/rschio, I do enjoy your blog and this module :-) thanks!

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/yourbasic/graph/pull/8#issuecomment-855229040, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACVN3SY2HSIZ5A4JY6UC2A3TRIF3JANCNFSM4RKPLHCA .