3 ms·
One, each core has to know about the other cores' search space and avoid it (to avoid duplicating effort) so you will contend on some sort of 'visited node' cac
by desdiv 12y ago
One, each core has to know about the other cores' search space and avoid it (to avoid duplicating effort) so you will contend on some sort of 'visited node' cache.
Just make the visited node cache public and immutable.
Two, the graph your building itself must be shared, obvs.
If the graph is immutable then there's zero problem with it being shared.
- jerven 12y agoYou can't make the cache immutable because then it will be empty at start and stays that way ;) The cache has to mutate and be shared as that's the work completed list. As each thread completes a bit of work (visits a node) it needs to communicate it with the other threads.
- desdiv 12y agoIn Scala, its: var cache = Seq(1,2,3) cache :+= 4 The cache is immutable and freely shareable. Any other thread and come in and read it and be guaranteed that its current state is valid.
- jerven 12y ago:+= Returns A copy of this sequence with an element appended. Meaning the cache is no longer shared as all threads end up having a thread local cache. You can't update shared changing state and have immutability at the same time. Immutability is great when one can have it but sometimes its not possible. Shared changing state is something to be avoid as much as possible but sometimes we need it.
- fijal 12y agohow do you make an immutable cache that you're populating all the time? (same goes for the graph)
- nickbauman 12y agoIf it's public and immutable each core will get only its own cache, which would be pointless. I like your thinking, though; perhaps there can be a way to always pass the last 'visited node' cache around in a timely way.