Subject: Re: bug#50672: nnpack is not reproducible

From: Kyle Meyer <[email-masked]>
Date: Fri, 22 Oct 2021 23:32:50 -0400

Ludovic Courtès writes:

> For the record, I tried the attached patch in an attempt to sort things
> as discussed in the issue above, but it doesn’t have the intended
> effect.  There must be other unsorted dictionaries elsewhere.

Hmm, I don't think dictionaries are a likely culprit here because
Python's dict implementation preserves the insertion order as of Python
v3.6 (and that behavior is declared as part of the language spec with
v3.7).

> diff --git a/peachpy/name.py b/peachpy/name.py
> index b6a03dc..c069fc2 100644
> --- a/peachpy/name.py
> +++ b/peachpy/name.py
> @@ -95,6 +95,10 @@ class Namespace:
>              self.prenames[scope_name.prename].add(scope)
>  
>      def assign_names(self):
> +        # Step 0: sort the dictionary for deterministic output
> +        self.prenames = dict(sorted(self.prenames.items(),
> +                                    key=lambda item: "" if item[0] == None else item[0]))
> +

In cases where the order of the keys isn't specified (i.e. Python 3.5
and below), I think the end result after your change is the same: it
creates a new dictionary for sorted _input_, but things won't
necessarily come out in the same order.

I'm not familiar with PeachPy, but taking a peek at name.py, the sets
used for the values of the prenames dictionary could be the problem.
And if that's the case, one solution would be switching those values
from sets to dictionaries.

With the change below (on top of PeachPy's 257881e), nnpack builds
reliably for me across a couple of attempts:

  $ guix-dev build --with-git-url=python-peachpy=$local --no-grafts --check nnpack
  successfully built /gnu/store/7z4nl55gssrf9na7wsvmw1dsqgawnj2p-nnpack-0.0-1.c07e3a0.drv
  successfully built /gnu/store/7z4nl55gssrf9na7wsvmw1dsqgawnj2p-nnpack-0.0-1.c07e3a0.drv
  /gnu/store/4ihjil42fbk53q73gpvdakynbv9q5q09-nnpack-0.0-1.c07e3a0

diff --git a/peachpy/name.py b/peachpy/name.py
index b6a03dc..412079d 100644
--- a/peachpy/name.py
+++ b/peachpy/name.py
@@ -86,13 +86,13 @@ def add_scoped_name(self, scoped_name):
                 self.names[scope_name.name] = scope
         else:
             assert scope_name.name is None
-            self.prenames.setdefault(scope_name.prename, set())
+            self.prenames.setdefault(scope_name.prename, {})
             if subscoped_name:
                 for subscope in iter(self.prenames[scope_name.prename]):
                     if isinstance(subscope, Namespace) and subscope.scope_name is scope_name:
                         subscope.add_scoped_name(subscoped_name)
                         return
-            self.prenames[scope_name.prename].add(scope)
+            self.prenames[scope_name.prename][scope] = None
 
     def assign_names(self):
         # Step 1: assign names to symbols with prenames with no conflicts