diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
index 2785b64..c83ed98 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
@@ -72,9 +72,6 @@
       o1 = SkylarkType.convertToSkylark(o1, /*env=*/ null);
       o2 = SkylarkType.convertToSkylark(o2, /*env=*/ null);
 
-      if (o1 instanceof ClassObject && o2 instanceof ClassObject) {
-        throw new ComparisonException("Cannot compare structs");
-      }
       if (o1 instanceof SkylarkNestedSet && o2 instanceof SkylarkNestedSet) {
         throw new ComparisonException("Cannot compare sets");
       }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
index 7ca5793..5748f63 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
@@ -801,7 +801,7 @@
     ImmutableList.Builder<Object> posargs = new ImmutableList.Builder<>();
     // We copy this into an ImmutableMap in the end, but we can't use an ImmutableMap.Builder, or
     // we'd still have to have a HashMap on the side for the sake of properly handling duplicates.
-    Map<String, Object> kwargs = new LinkedHashMap<>();
+    Map<String, Object> kwargs = new HashMap<>();
     BaseFunction function = checkCallable(funcValue, getLocation());
     evalArguments(posargs, kwargs, env);
     return function.call(posargs.build(), ImmutableMap.copyOf(kwargs), this, env);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
index cf371af..6ae2ae5 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
@@ -18,8 +18,8 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.syntax.SkylarkMutable.MutableMap;
-import java.util.LinkedHashMap;
 import java.util.Map;
+import java.util.TreeMap;
 import javax.annotation.Nullable;
 
 /**
@@ -46,7 +46,7 @@
 public final class SkylarkDict<K, V>
     extends MutableMap<K, V> implements Map<K, V>, SkylarkIndexable {
 
-  private final LinkedHashMap<K, V> contents = new LinkedHashMap<>();
+  private final TreeMap<K, V> contents = new TreeMap<>(EvalUtils.SKYLARK_COMPARATOR);
 
   private final Mutability mutability;
 
@@ -139,7 +139,7 @@
 
   /** @return the first key in the dict */
   K firstKey() {
-    return contents.entrySet().iterator().next().getKey();
+    return contents.firstKey();
   }
 
   /**