Skip to content

mutate: replace_element_with_copy no longer reproducible under a fixed rand seed (source drawn from unordered pointer set) #626

Description

@domg123

Since 81.2.5 (#624), replace_element_with_copy draws its copy source from anywhere in the tree rather than just siblings — a great capability for GP (it effectively gives mutate a native subtree-graft move). However, the source node is selected by indexing into ValuesFromTreeData::allNodes, which is an EvaluableNode::ReferenceSetType — an unordered set keyed on node pointers. Its iteration order depends on the nodes' memory addresses, so the same random seed selects a different source node depending on allocation history. mutate is therefore no longer reproducible under set_rand_seed.

Because replace_element_with_copy is part of the default operation-type split, this affects every mutate/mutate_entity call, not just callers that opt into the op.

Repro

Two identical (set_rand_seed "fixed") + (mutate ...) calls, separated only by allocation churn (unrelated mutates whose results are discarded), return different results:

(seq
	(declare (assoc
			mutate_fixed (lambda (seq
				(set_rand_seed "fixed")
				(unparse (mutate
					(parse "(+ (* x x) (sin (* x x)) (- (/ y 2) 7))")
					0.5
					(assoc "symbol" 0.5 "number" 0.5)
					(assoc "replace_element_with_copy" 1.0)))))
		)
		(declare (assoc a (call mutate_fixed))
			;; allocation churn: unrelated mutates whose results are discarded
			(map
				(lambda (mutate
					(parse "(+ (* x x) (sin (* x x)) (- (/ y 2) 7))")
					0.5
					(assoc "symbol" 0.5 "number" 0.5)
					.null))
				(range 0 200))
			(declare (assoc b (call mutate_fixed))
				(print "a:         " a "\n")
				(print "b:         " b "\n")
				(print "identical: " (= a b) "\n")))))

On the 81.3.0 darwin-arm64 release binary (amalgam-st):

a:         (+ (* (- (/ y 2) 7) x x) (- (/ (* x x) 2) 17) (sin (+ (* x x) (- (/ y 2) 7) (sin (* x x)))))
b:         (+ (* (sin (* x x)) x x) (- (/ 2 2) 17) (sin x))
identical: .false

Same script on 81.1.1: identical: .true.

Downstream this shows up as flaky same-seed test failures: which tests fail changes from run to run, since the divergence depends on allocation layout at the moment the op fires.

Suggested fix

In GetStringsFromTree, also collect nodes into a std::vector<EvaluableNode *> in traversal order (keeping the existing set for the already-visited check on cyclic structures), and have ENBISI_replace_element_with_copy index into that vector. Traversal order is structural, so selection becomes deterministic again — and indexing the vector is O(1) instead of the current O(n) walk over the set.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions