LdDl / ch

Contraction Hierarchies (with bidirectional version of Dijkstra's algorithm) technique for computing shortest path in graph.
Apache License 2.0
46 stars 5 forks source link

Remove pointer slices and increase performance #37

Closed mertakman closed 1 year ago

mertakman commented 1 year ago

https://medium.com/@philpearl/bad-go-slices-of-pointers-ed3c06b8bb41 Using pointers with slices in Golang often causes bad errors since the slices are pointers by default. When iterating them , it bloats L caches and prevents them from caching the page of slice which will increase iteration and lookup performance . Benchmarks with previous and current version is : Previous version:

Fixed Version:

Difference:

LdDl commented 1 year ago

That's interesting anyways despite you closed PR :) I guess it will be reopened later?

There is a comment section in that article and sometimes storing Values instead of Pointers could lead to some problems: https://go.dev/play/p/lk7s0IO7-WY. But, in case of identifier term for vertex it's not a case I believe