specs: use lazy lexicographic comparison instead of key_ordering

We have been using the `@llnl.util.lang.key_ordering` decorator for specs
and most of their components. This leverages the fact that in Python,
tuple comparison is lexicographic. It allows you to implement a
`_cmp_key` method on your class, and have `__eq__`, `__lt__`, etc.
implemented automatically using that key. For example, you might use
tuple keys to implement comparison, e.g.:

```python
class Widget:
    # author implements this
    def _cmp_key(self):
        return (
            self.a,
            self.b,
            (self.c, self.d),
            self.e
        )

    # operators are generated by @key_ordering
    def __eq__(self, other):
        return self._cmp_key() == other._cmp_key()

    def __lt__(self):
        return self._cmp_key() < other._cmp_key()

    # etc.
```

The issue there for simple comparators is that we have to bulid the
tuples *and* we have to generate all the values in them up front. When
implementing comparisons for large data structures, this can be costly.

This PR replaces `@key_ordering` with a new decorator,
`@lazy_lexicographic_ordering`. Lazy lexicographic comparison maps the
tuple comparison shown above to generator functions. Instead of comparing
based on pre-constructed tuple keys, users of this decorator can compare
using elements from a generator. So, you'd write:

```python
@lazy_lexicographic_ordering
class Widget:
    def _cmp_iter(self):
        yield a
        yield b
        def cd_fun():
            yield c
            yield d
        yield cd_fun
        yield e

    # operators are added by decorator (but are a bit more complex)

There are no tuples that have to be pre-constructed, and the generator
does not have to complete. Instead of tuples, we simply make functions
that lazily yield what would've been in the tuple. If a yielded value is
a `callable`, the comparison functions will call it and recursively
compar it. The comparator just walks the data structure like you'd expect
it to.

The ``@lazy_lexicographic_ordering`` decorator handles the details of
implementing comparison operators, and the ``Widget`` implementor only
has to worry about writing ``_cmp_iter``, and making sure the elements in
it are also comparable.

Using this PR shaves another 1.5 sec off the runtime of `spack buildcache
list`, and it also speeds up Spec comparison by about 30%. The runtime
improvement comes mostly from *not* calling `hash()` `_cmp_iter()`.

5 files changed, 340 insertions, 155 deletions

diff --git a/lib/spack/llnl/util/lang.py b/lib/spack/llnl/util/lang.py
index 17c1fe8427..4097e4bf6f 100644
--- a/lib/spack/llnl/util/lang.py
+++ b/lib/spack/llnl/util/lang.py
@@ -14,6 +14,11 @@ from datetime import datetime, timedelta
 from six import string_types
 import sys
 
+if sys.version_info < (3, 0):
+    from itertools import izip_longest  # novm
+    zip_longest = izip_longest
+else:
+    from itertools import zip_longest  # novm
 
 if sys.version_info >= (3, 3):
     from collections.abc import Hashable, MutableMapping  # novm
@@ -227,48 +232,222 @@ def list_modules(directory, **kwargs):
                 yield re.sub('.py$', '', name)
 
 
-def key_ordering(cls):
-    """Decorates a class with extra methods that implement rich comparison
-       operations and ``__hash__``.  The decorator assumes that the class
-       implements a function called ``_cmp_key()``.  The rich comparison
-       operations will compare objects using this key, and the ``__hash__``
-       function will return the hash of this key.
+def decorator_with_or_without_args(decorator):
+    """Allows a decorator to be used with or without arguments, e.g.::
+
+        # Calls the decorator function some args
+        @decorator(with, arguments, and=kwargs)
+
+    or::
+
+        # Calls the decorator function with zero arguments
+        @decorator
+
+    """
+    # See https://stackoverflow.com/questions/653368 for more on this
+    @functools.wraps(decorator)
+    def new_dec(*args, **kwargs):
+        if len(args) == 1 and len(kwargs) == 0 and callable(args[0]):
+            # actual decorated function
+            return decorator(args[0])
+        else:
+            # decorator arguments
+            return lambda realf: decorator(realf, *args, **kwargs)
+
+    return new_dec
+
+
+#: sentinel for testing that iterators are done in lazy_lexicographic_ordering
+done = object()
+
+
+def tuplify(seq):
+    """Helper for lazy_lexicographic_ordering()."""
+    return tuple((tuplify(x) if callable(x) else x) for x in seq())
+
+
+def lazy_eq(lseq, rseq):
+    """Equality comparison for two lazily generated sequences.
+
+    See ``lazy_lexicographic_ordering``.
+    """
+    liter = lseq()  # call generators
+    riter = rseq()
+
+    # zip_longest is implemented in native code, so use it for speed.
+    # use zip_longest instead of zip because it allows us to tell
+    # which iterator was longer.
+    for left, right in zip_longest(liter, riter, fillvalue=done):
+        if (left is done) or (right is done):
+            return False
+
+        # recursively enumerate any generators, otherwise compare
+        equal = lazy_eq(left, right) if callable(left) else left == right
+        if not equal:
+            return False
+
+    return True
 
-       If a class already has ``__eq__``, ``__ne__``, ``__lt__``, ``__le__``,
-       ``__gt__``, or ``__ge__`` defined, this decorator will overwrite them.
 
-       Raises:
-           TypeError: If the class does not have a ``_cmp_key`` method
+def lazy_lt(lseq, rseq):
+    """Less-than comparison for two lazily generated sequences.
+
+    See ``lazy_lexicographic_ordering``.
     """
-    def setter(name, value):
-        value.__name__ = name
-        setattr(cls, name, value)
-
-    if not has_method(cls, '_cmp_key'):
-        raise TypeError("'%s' doesn't define _cmp_key()." % cls.__name__)
-
-    setter('__eq__',
-           lambda s, o:
-           (s is o) or (o is not None and s._cmp_key() == o._cmp_key()))
-    setter('__lt__',
-           lambda s, o: o is not None and s._cmp_key() < o._cmp_key())
-    setter('__le__',
-           lambda s, o: o is not None and s._cmp_key() <= o._cmp_key())
-
-    setter('__ne__',
-           lambda s, o:
-           (s is not o) and (o is None or s._cmp_key() != o._cmp_key()))
-    setter('__gt__',
-           lambda s, o: o is None or s._cmp_key() > o._cmp_key())
-    setter('__ge__',
-           lambda s, o: o is None or s._cmp_key() >= o._cmp_key())
-
-    setter('__hash__', lambda self: hash(self._cmp_key()))
+    liter = lseq()
+    riter = rseq()
+
+    for left, right in zip_longest(liter, riter, fillvalue=done):
+        if (left is done) or (right is done):
+            return left is done  # left was shorter than right
+
+        sequence = callable(left)
+        equal = lazy_eq(left, right) if sequence else left == right
+        if equal:
+            continue
+
+        if sequence:
+            return lazy_lt(left, right)
+        if left is None:
+            return True
+        if right is None:
+            return False
+
+        return left < right
+
+    return False  # if equal, return False
+
+
+@decorator_with_or_without_args
+def lazy_lexicographic_ordering(cls, set_hash=True):
+    """Decorates a class with extra methods that implement rich comparison.
+
+    This is a lazy version of the tuple comparison used frequently to
+    implement comparison in Python. Given some objects with fields, you
+    might use tuple keys to implement comparison, e.g.::
+
+        class Widget:
+            def _cmp_key(self):
+                return (
+                    self.a,
+                    self.b,
+                    (self.c, self.d),
+                    self.e
+                )
+
+            def __eq__(self, other):
+                return self._cmp_key() == other._cmp_key()
+
+            def __lt__(self):
+                return self._cmp_key() < other._cmp_key()
+
+            # etc.
+
+    Python would compare ``Widgets`` lexicographically based on their
+    tuples. The issue there for simple comparators is that we have to
+    bulid the tuples *and* we have to generate all the values in them up
+    front. When implementing comparisons for large data structures, this
+    can be costly.
+
+    Lazy lexicographic comparison maps the tuple comparison shown above
+    to generator functions. Instead of comparing based on pre-constructed
+    tuple keys, users of this decorator can compare using elements from a
+    generator. So, you'd write::
+
+        @lazy_lexicographic_ordering
+        class Widget:
+            def _cmp_iter(self):
+                yield a
+                yield b
+                def cd_fun():
+                    yield c
+                    yield d
+                yield cd_fun
+                yield e
+
+            # operators are added by decorator
+
+    There are no tuples preconstructed, and the generator does not have
+    to complete. Instead of tuples, we simply make functions that lazily
+    yield what would've been in the tuple. The
+    ``@lazy_lexicographic_ordering`` decorator handles the details of
+    implementing comparison operators, and the ``Widget`` implementor
+    only has to worry about writing ``_cmp_iter``, and making sure the
+    elements in it are also comparable.
+
+    Some things to note:
+
+      * If a class already has ``__eq__``, ``__ne__``, ``__lt__``,
+        ``__le__``, ``__gt__``, ``__ge__``, or ``__hash__`` defined, this
+        decorator will overwrite them.
+
+      * If ``set_hash`` is ``False``, this will not overwrite
+        ``__hash__``.
+
+      * This class uses Python 2 None-comparison semantics. If you yield
+        None and it is compared to a non-None type, None will always be
+        less than the other object.
+
+    Raises:
+        TypeError: If the class does not have a ``_cmp_iter`` method
+
+    """
+    if not has_method(cls, "_cmp_iter"):
+        raise TypeError("'%s' doesn't define _cmp_iter()." % cls.__name__)
+
+    # comparison operators are implemented in terms of lazy_eq and lazy_lt
+    def eq(self, other):
+        if self is other:
+            return True
+        return (other is not None) and lazy_eq(self._cmp_iter, other._cmp_iter)
+
+    def lt(self, other):
+        if self is other:
+            return False
+        return (other is not None) and lazy_lt(self._cmp_iter, other._cmp_iter)
+
+    def ne(self, other):
+        if self is other:
+            return False
+        return (other is None) or not lazy_eq(self._cmp_iter, other._cmp_iter)
+
+    def gt(self, other):
+        if self is other:
+            return False
+        return (other is None) or lazy_lt(other._cmp_iter, self._cmp_iter)
+
+    def le(self, other):
+        if self is other:
+            return True
+        return (other is not None) and not lazy_lt(other._cmp_iter,
+                                                   self._cmp_iter)
+
+    def ge(self, other):
+        if self is other:
+            return True
+        return (other is None) or not lazy_lt(self._cmp_iter, other._cmp_iter)
+
+    def h(self):
+        return hash(tuplify(self._cmp_iter))
+
+    def add_func_to_class(name, func):
+        """Add a function to a class with a particular name."""
+        func.__name__ = name
+        setattr(cls, name, func)
+
+    add_func_to_class("__eq__", eq)
+    add_func_to_class("__ne__", ne)
+    add_func_to_class("__lt__", lt)
+    add_func_to_class("__le__", le)
+    add_func_to_class("__gt__", gt)
+    add_func_to_class("__ge__", ge)
+    if set_hash:
+        add_func_to_class("__hash__", h)
 
     return cls
 
 
-@key_ordering
+@lazy_lexicographic_ordering
 class HashableMap(MutableMapping):
     """This is a hashable, comparable dictionary.  Hash is performed on
        a tuple of the values in the dictionary."""
@@ -291,8 +470,9 @@ class HashableMap(MutableMapping):
     def __delitem__(self, key):
         del self.dict[key]
 
-    def _cmp_key(self):
-        return tuple(sorted(self.values()))
+    def _cmp_iter(self):
+        for _, v in sorted(self.items()):
+            yield v
 
     def copy(self):
         """Type-agnostic clone method.  Preserves subclass type."""
diff --git a/lib/spack/spack/architecture.py b/lib/spack/spack/architecture.py
index 6341df857d..ba2d824010 100644
--- a/lib/spack/spack/architecture.py
+++ b/lib/spack/spack/architecture.py
@@ -65,7 +65,7 @@ import archspec.cpu
 import six
 
 import llnl.util.tty as tty
-from llnl.util.lang import memoized, list_modules, key_ordering
+import llnl.util.lang as lang
 
 import spack.compiler
 import spack.compilers
@@ -232,7 +232,7 @@ class Target(object):
         )
 
 
-@key_ordering
+@lang.lazy_lexicographic_ordering
 class Platform(object):
     """ Abstract class that each type of Platform will subclass.
         Will return a instance of it once it is returned.
@@ -329,23 +329,27 @@ class Platform(object):
     def __str__(self):
         return self.name
 
-    def _cmp_key(self):
-        t_keys = ''.join(str(t._cmp_key()) for t in
-                         sorted(self.targets.values()))
-        o_keys = ''.join(str(o._cmp_key()) for o in
-                         sorted(self.operating_sys.values()))
-        return (self.name,
-                self.default,
-                self.front_end,
-                self.back_end,
-                self.default_os,
-                self.front_os,
-                self.back_os,
-                t_keys,
-                o_keys)
-
-
-@key_ordering
+    def _cmp_iter(self):
+        yield self.name
+        yield self.default
+        yield self.front_end
+        yield self.back_end
+        yield self.default_os
+        yield self.front_os
+        yield self.back_os
+
+        def targets():
+            for t in sorted(self.targets.values()):
+                yield t._cmp_iter
+        yield targets
+
+        def oses():
+            for o in sorted(self.operating_sys.values()):
+                yield o._cmp_iter
+        yield oses
+
+
+@lang.lazy_lexicographic_ordering
 class OperatingSystem(object):
     """ Operating System will be like a class similar to platform extended
         by subclasses for the specifics. Operating System will contain the
@@ -363,8 +367,9 @@ class OperatingSystem(object):
     def __repr__(self):
         return self.__str__()
 
-    def _cmp_key(self):
-        return (self.name, self.version)
+    def _cmp_iter(self):
+        yield self.name
+        yield self.version
 
     def to_dict(self):
         return syaml_dict([
@@ -373,7 +378,7 @@ class OperatingSystem(object):
         ])
 
 
-@key_ordering
+@lang.lazy_lexicographic_ordering
 class Arch(object):
     """Architecture is now a class to help with setting attributes.
 
@@ -423,20 +428,21 @@ class Arch(object):
                 self.target is not None)
     __bool__ = __nonzero__
 
-    def _cmp_key(self):
+    def _cmp_iter(self):
         if isinstance(self.platform, Platform):
-            platform = self.platform.name
+            yield self.platform.name
         else:
-            platform = self.platform
+            yield self.platform
+
         if isinstance(self.os, OperatingSystem):
-            os = self.os.name
+            yield self.os.name
         else:
-            os = self.os
+            yield self.os
+
         if isinstance(self.target, Target):
-            target = self.target.microarchitecture
+            yield self.target.microarchitecture
         else:
-            target = self.target
-        return (platform, os, target)
+            yield self.target
 
     def to_dict(self):
         str_or_none = lambda v: str(v) if v else None
@@ -458,7 +464,7 @@ class Arch(object):
         return arch_for_spec(spec)
 
 
-@memoized
+@lang.memoized
 def get_platform(platform_name):
     """Returns a platform object that corresponds to the given name."""
     platform_list = all_platforms()
@@ -494,13 +500,13 @@ def arch_for_spec(arch_spec):
     return Arch(arch_plat, arch_spec.os, arch_spec.target)
 
 
-@memoized
+@lang.memoized
 def _all_platforms():
     classes = []
     mod_path = spack.paths.platform_path
     parent_module = "spack.platforms"
 
-    for name in list_modules(mod_path):
+    for name in lang.list_modules(mod_path):
         mod_name = '%s.%s' % (parent_module, name)
         class_name = mod_to_class(name)
         mod = __import__(mod_name, fromlist=[class_name])
@@ -515,7 +521,7 @@ def _all_platforms():
     return classes
 
 
-@memoized
+@lang.memoized
 def _platform():
     """Detects the platform for this machine.
 
@@ -546,7 +552,7 @@ platform = _platform
 all_platforms = _all_platforms
 
 
-@memoized
+@lang.memoized
 def default_arch():
     """Default ``Arch`` object for this machine.
 
@@ -570,7 +576,7 @@ def sys_type():
     return str(default_arch())
 
 
-@memoized
+@lang.memoized
 def compatible_sys_types():
     """Returns a list of all the systypes compatible with the current host."""
     compatible_archs = []
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index e43947b60b..370a5d2f0c 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -203,7 +203,7 @@ def colorize_spec(spec):
     return clr.colorize(re.sub(_separators, insert_color(), str(spec)) + '@.')
 
 
-@lang.key_ordering
+@lang.lazy_lexicographic_ordering
 class ArchSpec(object):
     def __init__(self, spec_or_platform_tuple=(None, None, None)):
         """ Architecture specification a package should be built with.
@@ -252,8 +252,10 @@ class ArchSpec(object):
             return spec_like
         return ArchSpec(spec_like)
 
-    def _cmp_key(self):
-        return self.platform, self.os, self.target
+    def _cmp_iter(self):
+        yield self.platform
+        yield self.os
+        yield self.target
 
     def _dup(self, other):
         self.platform = other.platform
@@ -534,7 +536,7 @@ class ArchSpec(object):
         return string in str(self) or string in self.target
 
 
-@lang.key_ordering
+@lang.lazy_lexicographic_ordering
 class CompilerSpec(object):
     """The CompilerSpec field represents the compiler or range of compiler
        versions that a package should be built with.  CompilerSpecs have a
@@ -623,8 +625,9 @@ class CompilerSpec(object):
         clone.versions = self.versions.copy()
         return clone
 
-    def _cmp_key(self):
-        return (self.name, self.versions)
+    def _cmp_iter(self):
+        yield self.name
+        yield self.versions
 
     def to_dict(self):
         d = syaml.syaml_dict([('name', self.name)])
@@ -648,7 +651,7 @@ class CompilerSpec(object):
         return str(self)
 
 
-@lang.key_ordering
+@lang.lazy_lexicographic_ordering
 class DependencySpec(object):
     """DependencySpecs connect two nodes in the DAG, and contain deptypes.
 
@@ -686,10 +689,10 @@ class DependencySpec(object):
             self.deptypes + dp.canonical_deptype(type)
         )
 
-    def _cmp_key(self):
-        return (self.parent.name if self.parent else None,
-                self.spec.name if self.spec else None,
-                self.deptypes)
+    def _cmp_iter(self):
+        yield self.parent.name if self.parent else None
+        yield self.spec.name if self.spec else None
+        yield self.deptypes
 
     def __str__(self):
         return "%s %s--> %s" % (self.parent.name if self.parent else None,
@@ -747,8 +750,15 @@ class FlagMap(lang.HashableMap):
             clone[name] = value
         return clone
 
-    def _cmp_key(self):
-        return tuple((k, tuple(v)) for k, v in sorted(six.iteritems(self)))
+    def _cmp_iter(self):
+        for k, v in sorted(self.items()):
+            yield k
+
+            def flags():
+                for flag in v:
+                    yield flag
+
+            yield flags
 
     def __str__(self):
         sorted_keys = [k for k in sorted(self.keys()) if self[k] != []]
@@ -1016,7 +1026,7 @@ class SpecBuildInterface(lang.ObjectWrapper):
         )
 
 
-@lang.key_ordering
+@lang.lazy_lexicographic_ordering(set_hash=False)
 class Spec(object):
 
     #: Cache for spec's prefix, computed lazily in the corresponding property
@@ -1060,7 +1070,7 @@ class Spec(object):
 
         self._hash = None
         self._build_hash = None
-        self._cmp_key_cache = None
+        self._dunder_hash = None
         self._package = None
 
         # Most of these are internal implementation details that can be
@@ -3358,7 +3368,7 @@ class Spec(object):
                 before possibly copying the dependencies of ``other`` onto
                 ``self``
             caches (bool or None): preserve cached fields such as
-                ``_normal``, ``_hash``, and ``_cmp_key_cache``. By
+                ``_normal``, ``_hash``, and ``_dunder_hash``. By
                 default this is ``False`` if DAG structure would be
                 changed by the copy, ``True`` if it's an exact copy.
 
@@ -3432,13 +3442,13 @@ class Spec(object):
         if caches:
             self._hash = other._hash
             self._build_hash = other._build_hash
-            self._cmp_key_cache = other._cmp_key_cache
+            self._dunder_hash = other._dunder_hash
             self._normal = other._normal
             self._full_hash = other._full_hash
         else:
             self._hash = None
             self._build_hash = None
-            self._cmp_key_cache = None
+            self._dunder_hash = None
             self._normal = False
             self._full_hash = None
 
@@ -3562,13 +3572,17 @@ class Spec(object):
         deps = self.flat_dependencies()
         return tuple(deps[name] for name in sorted(deps))
 
-    def _eq_dag(self, other, vs, vo, deptypes):
-        """Recursive helper for eq_dag and ne_dag.  Does the actual DAG
-           traversal."""
+    def eq_dag(self, other, deptypes=True, vs=None, vo=None):
+        """True if the full dependency DAGs of specs are equal."""
+        if vs is None:
+            vs = set()
+        if vo is None:
+            vo = set()
+
         vs.add(id(self))
         vo.add(id(other))
 
-        if self.ne_node(other):
+        if not self.eq_node(other):
             return False
 
         if len(self._dependencies) != len(other._dependencies):
@@ -3596,58 +3610,38 @@ class Spec(object):
                 continue
 
             # Recursive check for equality
-            if not s._eq_dag(o, vs, vo, deptypes):
+            if not s.eq_dag(o, deptypes, vs, vo):
                 return False
 
         return True
 
-    def eq_dag(self, other, deptypes=True):
-        """True if the full dependency DAGs of specs are equal."""
-        return self._eq_dag(other, set(), set(), deptypes)
-
-    def ne_dag(self, other, deptypes=True):
-        """True if the full dependency DAGs of specs are not equal."""
-        return not self.eq_dag(other, set(), set(), deptypes)
-
     def _cmp_node(self):
-        """Comparison key for just *this node* and not its deps."""
-        # Name or namespace None will lead to invalid comparisons for abstract
-        # specs. Replace them with the empty string, which is not a valid spec
-        # name nor namespace so it will not create spurious equalities.
-        return (self.name or '',
-                self.namespace or '',
-                tuple(self.versions),
-                self.variants,
-                self.architecture,
-                self.compiler,
-                self.compiler_flags)
+        """Yield comparable elements of just *this node* and not its deps."""
+        yield self.name or ''
+        yield self.namespace or ''
+        yield self.versions
+        yield self.variants
+        yield self.compiler
+        yield self.compiler_flags
+        yield self.architecture
 
     def eq_node(self, other):
         """Equality with another spec, not including dependencies."""
-        return self._cmp_node() == other._cmp_node()
-
-    def ne_node(self, other):
-        """Inequality with another spec, not including dependencies."""
-        return self._cmp_node() != other._cmp_node()
-
-    def _cmp_key(self):
-        """This returns a key for the spec *including* DAG structure.
+        return (other is not None) and lang.lazy_eq(
+            self._cmp_node, other._cmp_node
+        )
 
-        The key is the concatenation of:
-          1. A tuple describing this node in the DAG.
-          2. The hash of each of this node's dependencies' cmp_keys.
-        """
-        if self._cmp_key_cache:
-            return self._cmp_key_cache
+    def _cmp_iter(self):
+        """Lazily yield components of self for comparison."""
+        for item in self._cmp_node():
+            yield item
 
-        dep_tuple = tuple(
-            (d.spec.name, hash(d.spec), tuple(sorted(d.deptypes)))
-            for name, d in sorted(self._dependencies.items()))
-
-        key = (self._cmp_node(), dep_tuple)
-        if self._concrete:
-            self._cmp_key_cache = key
-        return key
+        def deps():
+            for _, dep in sorted(self._dependencies.items()):
+                yield dep.spec.name
+                yield tuple(sorted(dep.deptypes))
+                yield hash(dep.spec)
+        yield deps
 
     def colorized(self):
         return colorize_spec(self)
@@ -4339,6 +4333,22 @@ class Spec(object):
             if hasattr(self, attr):
                 setattr(self, attr, None)
 
+    def __hash__(self):
+        # If the spec is concrete, we leverage the DAG hash and just use
+        # a 64-bit prefix of it. The DAG hash has the advantage that it's
+        # computed once per concrete spec, and it's saved -- so if we
+        # read concrete specs we don't need to recompute the whole hash.
+        # This is good for large, unchanging specs.
+        if self.concrete:
+            if not self._dunder_hash:
+                self._dunder_hash = self.dag_hash_bit_prefix(64)
+            return self._dunder_hash
+
+        # This is the normal hash for lazy_lexicographic_ordering. It's
+        # slow for large specs because it traverses the whole spec graph,
+        # so we hope it only runs on abstract specs, which are small.
+        return hash(lang.tuplify(self._cmp_iter))
+
 
 class LazySpecCache(collections.defaultdict):
     """Cache for Specs that uses a spec_like as key, and computes lazily
diff --git a/lib/spack/spack/test/spec_syntax.py b/lib/spack/spack/test/spec_syntax.py
index a523dffca8..fd5108c809 100644
--- a/lib/spack/spack/test/spec_syntax.py
+++ b/lib/spack/spack/test/spec_syntax.py
@@ -352,10 +352,10 @@ class TestSpecSyntax(object):
     def test_ambiguous_hash(self, mutable_database):
         x1 = Spec('a')
         x1.concretize()
-        x1._hash = 'xy'
+        x1._hash = 'xyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy'
         x2 = Spec('a')
         x2.concretize()
-        x2._hash = 'xx'
+        x2._hash = 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'
 
         mutable_database.add(x1, spack.store.layout)
         mutable_database.add(x2, spack.store.layout)
@@ -557,10 +557,6 @@ class TestSpecSyntax(object):
         with specfile.open('w') as f:
             f.write(s['libelf'].to_yaml(hash=ht.build_hash))
 
-        print("")
-        print("")
-        print("PARSING HERE")
-
         # Make sure we can use yaml path as dependency, e.g.:
         #     "spack spec libdwarf ^ /path/to/libelf.yaml"
         specs = sp.parse('libdwarf ^ {0}'.format(specfile.strpath))
diff --git a/lib/spack/spack/variant.py b/lib/spack/spack/variant.py
index be3b74b97d..0929a5ea44 100644
--- a/lib/spack/spack/variant.py
+++ b/lib/spack/spack/variant.py
@@ -201,7 +201,7 @@ def implicit_variant_conversion(method):
     return convert
 
 
-@lang.key_ordering
+@lang.lazy_lexicographic_ordering
 class AbstractVariant(object):
     """A variant that has not yet decided who it wants to be. It behaves like
     a multi valued variant which **could** do things.
@@ -282,21 +282,14 @@ class AbstractVariant(object):
         # to a set
         self._value = tuple(sorted(set(value)))
 
-    def _cmp_value(self):
-        """Returns a tuple of strings containing the values stored in
-        the variant.
+    def _cmp_iter(self):
+        yield self.name
 
-        Returns:
-            tuple of str: values stored in the variant
-        """
         value = self._value
         if not isinstance(value, tuple):
             value = (value,)
-        stringified = tuple(str(x) for x in value)
-        return stringified
-
-    def _cmp_key(self):
-        return self.name, self._cmp_value()
+        value = tuple(str(x) for x in value)
+        yield value
 
     def copy(self):
         """Returns an instance of a variant equivalent to self