Godot Version
4.5
Question
My game involves modifying a graph, and the game needs to calculate some statistics about the graph, which can be very slow depending on the number of edges, E. My idea about how to speed this up is to calculate the statistic as if the graph had just 1 edge, then 2, up to E, overwriting the current state of the statistic along the way. We only care about the modal trail length up to 11, so once we’ve added in just a random couple edges, the answer is good enough for us, but we continue counting so we can draw a pretty chart. This is still extremely slow, and it would be ugly to start and stop calculations in the middle of each frame, so the idea is to do all the math in a separate thread, with a mutex guarding the statistic. Whenever I’m done with each successive level of detail, I get the lock, check if the graph hasn’t been changed, and if it hasn’t then the new result is valid, so I update the result, otherwise we return. Whenever I need to check the statistic, I get the lock and then duplicate it
I thought this would be safe enough, but very rarely my game has been crashing, perhaps the issue is that I don’t first signal to any running threads from prior changes that I’m about to change the graph, and there’s a race when I try to get the connections for each vertex? The count_trails_from_length_withoutfunction that recursively calls itself is what is extremely slow, and I’m not sure what sort of concurrency primitives are best to signal to it without blocking for too long so I can make changes from the main thread without waiting for slow calculations to complete
func _ready() -> void:
thread_mu = Mutex.new()
density_mu = Mutex.new()
func _exit_tree() -> void:
if last_thread != null:
# i'm not fully sure about wait_to_finish
last_thread.wait_to_finish()
var thread_mu: Mutex
var last_thread = null
var density_mu: Mutex
var densities: Array[float] = []
var density_iteration: int = 0
## this is our getter for ui and game logic that allows us to look at the densities, which may have calculations in progress
func view_densities():
density_mu.lock()
var dcopy = densities.duplicate()
density_mu.unlock()
return dcopy
## this is the entrypoint into spawning a new thread that i call whenever the graph changes
func find_densities():
thread_mu.lock()
var thread = Thread.new()
thread.start(_find_densities.bind(last_thread))
last_thread = thread
thread_mu.unlock()
func _find_densities(last_thr):
density_mu.lock()
var iteration = density_iteration + 1
density_iteration = iteration
density_mu.unlock()
var es = edges.duplicate()
var using = {}
for e in es:
using[e] = true
es.shuffle()
for e in es:
using.erase(e)
var res: Array[float] = []
for i in 12:
# it might be slightly more correct to check if it's invalid
# between each of these loops instead of all at the end, but in
# practice, the maximum length trails are the only ones that take
# a while to process
res.push_back(float(Graph.count_trails_length_k(i, using))) # line 139
density_mu.lock()
var ok = density_iteration == iteration
if ok:
densities = res
density_mu.unlock()
if !ok:
if last_thr != null:
# i'm not fully sure about wait to finish, i think this is
# fine and unrelated but i just threw them in here like this
# because if this current thread is not ok, then the last one
# should not be ok also, so it seems like it's not a big deal
# to wait for it
last_thr.wait_to_finish()
return
if last_thr != null:
last_thr.wait_to_finish()
func count_trails_length_k(k: int, without: Dictionary = {})-> int:
if k > len(edges):
return 0
if k == 0:
return 0
var count = 0
for v in vertices:
count += count_trails_from_length_without(v, k, without) # line 169
return count
func count_trails_from_length_without(v, k, using)->int:
if k == 0:
return 1
var count = 0
for n in v.connections.keys(): # line 176
var e = v.connections.get(n)
if using.get(e):
continue
using[e]=true
count += count_trails_from_length_without(n, k-1, using)
using.erase(e)
return count
These are the errors, I can’t reproduce really but my guess is at the start of the game when I algorithmically create an initial graph very fast, there’s a rare race condition involving concurrent access to a dictionary when the graph is changed while a calculation was happening in the background
E 0:00:00:566 graph.gd:176 @ count_trails_from_length_without(): FATAL: Index p_index = 1 is out of bounds (((Vector<T> *)(this))->_cowdata.size() = 1).
<C++ Source> ./core/templates/vector.h:54 @ operator[]()
<Stack Trace> graph.gd:176 @ count_trails_from_length_without()
graph.gd:169 @ count_trails_length_k()
graph.gd:139 @ _find_densities()
E 0:00:00:566 graph.gd:176 @ count_trails_from_length_without(): Caller thread can't call this function in this node (/root). Use call_deferred() or call_thread_group() instead.
<C++ Error> Condition "!is_accessible_from_caller_thread()" is true.
<C++ Source> scene/main/node.cpp:2552 @ propagate_notification()
<Stack Trace> graph.gd:176 @ count_trails_from_length_without()
graph.gd:169 @ count_trails_length_k()
graph.gd:139 @ _find_densities()
Thanks so much!