folks, backends: use "small sets" instead of hash sets most of the time

Notable exceptions are:

* sets of personas that are, or might be, the entire set from a backend
  (possible future refinement: use a SmallSet if there aren't many)

* sets of potentially many Individuals (likewise)

* the object cache (potentially pretty large)

* debug stuff (not relevant for performance)

* the set of IM addresses being matched (we want to keep this O(1),
  but it should be a GHashTable)

This speeds up tests/eds/perf by around 5%.

Bug: https://bugzilla.gnome.org/show_bug.cgi?id=687161
Reviewed-by: Philip Withnall <philip@tecnocode.co.uk>
[squashed in responses to review -smcv]
Signed-off-by: Simon McVittie <simon.mcvittie@collabora.co.uk>

6 files changed, 56 insertions, 55 deletions

diff --git a/folks/Makefile.am b/folks/Makefile.am
index 57c10f33..4d539aba 100644
--- a/folks/Makefile.am
+++ b/folks/Makefile.am
@@ -111,6 +111,7 @@ libfolks_la_VALAFLAGS = \
 	--vapidir=$(abs_builddir) \
 	--pkg build-conf \
 	--pkg folks-internal \
+	--pkg folks-generics \
 	--pkg gobject-2.0 \
 	--pkg gmodule-2.0 \
 	--pkg gio-2.0 \
diff --git a/folks/anti-linkable.vala b/folks/anti-linkable.vala
index 39b4e631..a53af5f2 100644
--- a/folks/anti-linkable.vala
+++ b/folks/anti-linkable.vala
@@ -115,7 +115,7 @@ public interface Folks.AntiLinkable : Folks.Persona
   public async void add_anti_links (Set<Persona> other_personas)
       throws PropertyError
     {
-      var new_anti_links = new HashSet<string> ();
+      var new_anti_links = new SmallSet<string> ();
       new_anti_links.add_all (this.anti_links);
 
       foreach (var p in other_personas)
@@ -148,7 +148,7 @@ public interface Folks.AntiLinkable : Folks.Persona
   public async void remove_anti_links (Set<Persona> other_personas)
       throws PropertyError
     {
-      var new_anti_links = new HashSet<string> ();
+      var new_anti_links = new SmallSet<string> ();
       new_anti_links.add_all (this.anti_links);
 
       foreach (var p in other_personas)
diff --git a/folks/backend-store.vala b/folks/backend-store.vala
index e7b5d695..0f47236b 100644
--- a/folks/backend-store.vala
+++ b/folks/backend-store.vala
@@ -44,9 +44,9 @@ public class Folks.BackendStore : Object {
   /* this contains all backends, regardless of enabled or prepared state */
   private HashMap<string,Backend> _backend_hash;
   /* if null, all backends are allowed */
-  private HashSet<string>? _backends_allowed;
+  private SmallSet<string>? _backends_allowed;
   /* if null, no backends are disabled */
-  private HashSet<string>? _backends_disabled;
+  private SmallSet<string>? _backends_disabled;
   private HashMap<string, Backend> _prepared_backends;
   private Map<string, Backend> _prepared_backends_ro;
   private File _config_file;
@@ -794,7 +794,7 @@ public class Folks.BackendStore : Object {
            * g_parse_debug_string(). */
           var tokens = envvar.split_set (" ,:");
 
-          this._backends_allowed = new HashSet<string> ();
+          this._backends_allowed = new SmallSet<string> ();
 
           foreach (unowned string s in tokens)
             {
@@ -827,7 +827,7 @@ public class Folks.BackendStore : Object {
         {
           var tokens = envvar.split_set (" ,:");
 
-          this._backends_disabled = new HashSet<string> ();
+          this._backends_disabled = new SmallSet<string> ();
 
           foreach (unowned string s in tokens)
             {
diff --git a/folks/individual-aggregator.vala b/folks/individual-aggregator.vala
index 705b34cd..84bb9e70 100644
--- a/folks/individual-aggregator.vala
+++ b/folks/individual-aggregator.vala
@@ -119,7 +119,7 @@ public class Folks.IndividualAggregator : Object
   private BackendStore _backend_store;
   private HashMap<string, PersonaStore> _stores;
   private unowned PersonaStore? _primary_store = null;
-  private HashSet<Backend> _backends;
+  private SmallSet<Backend> _backends;
 
   /* This is conceptually a MultiMap<string, Individual> but it's sufficiently
    * heavily-used that avoiding GObject overhead in favour of inlinable
@@ -360,7 +360,7 @@ public class Folks.IndividualAggregator : Object
       this._link_map = new HashTable<string, GenericArray<Individual>> (
           str_hash, str_equal);
 
-      this._backends = new HashSet<Backend> ();
+      this._backends = new SmallSet<Backend> ();
       this._debug = Debug.dup ();
       this._debug.print_status.connect (this._debug_print_status);
 
@@ -919,7 +919,7 @@ public class Folks.IndividualAggregator : Object
             }
 
           this._personas_changed_cb (store, persona_set,
-              new HashSet<Persona> (), null, null,
+              SmallSet.empty<Persona> (), null, null,
               GroupDetails.ChangeReason.NONE);
         }
 
@@ -976,8 +976,8 @@ public class Folks.IndividualAggregator : Object
         {
           removed_personas.add (iter.get_value ());
         }
-      this._personas_changed_cb (store, new HashSet<Persona> (), removed_personas,
-          null, null, GroupDetails.ChangeReason.NONE);
+      this._personas_changed_cb (store, SmallSet.empty<Persona> (),
+          removed_personas, null, null, GroupDetails.ChangeReason.NONE);
 
       if (this._primary_store == store)
         {
@@ -1019,8 +1019,8 @@ public class Folks.IndividualAggregator : Object
       Internal.profiling_point ("emitting " +
           "IndividualAggregator::individuals-changed");
 
-      _added = (added != null) ? (!) added : new HashSet<Individual> ();
-      _removed = (removed != null) ? (!) removed : new HashSet<Individual> ();
+      _added = (added != null) ? (!) added : SmallSet.empty<Individual> ();
+      _removed = (removed != null) ? (!) removed : SmallSet.empty<Individual> ();
 
       if (changes != null)
         {
@@ -1304,7 +1304,7 @@ public class Folks.IndividualAggregator : Object
           "(is user: %s, IID: %s).", pspec.name, persona.uid,
           persona.is_user ? "yes" : "no", persona.iid);
 
-      var persona_set = new HashSet<Persona> ();
+      var persona_set = new SmallSet<Persona> ();
       persona_set.add (persona);
 
       this._personas_changed_cb (persona.store, persona_set, persona_set,
@@ -1322,7 +1322,7 @@ public class Folks.IndividualAggregator : Object
       debug ("Anti-links changed for persona '%s' (is user: %s, IID: %s).",
           persona.uid, persona.is_user ? "yes" : "no", persona.iid);
 
-      var persona_set = new HashSet<Persona> ();
+      var persona_set = new SmallSet<Persona> ();
       persona_set.add (persona);
 
       this._personas_changed_cb (persona.store, persona_set, persona_set,
@@ -1833,7 +1833,7 @@ public class Folks.IndividualAggregator : Object
       if (i.personas.size > 0)
         {
           var changes = new HashMultiMap<Individual?, Individual?> ();
-          var individuals = new HashSet<Individual> ();
+          var individuals = new SmallSet<Individual> ();
 
           individuals.add (i);
           changes.set (i, replacement);
@@ -1943,7 +1943,9 @@ public class Folks.IndividualAggregator : Object
     {
       /* Removing personas changes the persona set so we need to make a copy
        * first */
-      var personas = new HashSet<Persona> ();
+      var personas = new SmallSet<Persona> ();
+      /* FIXME: this is O(n**2) but if we know that individual.personas
+       * is a SmallSet, we can do it in O(n) */
       foreach (var p in individual.personas)
         {
           personas.add (p);
@@ -2065,7 +2067,7 @@ public class Folks.IndividualAggregator : Object
             AbstractFieldDetails<string>.equal_static);
 
       /* List of local_ids */
-      var local_ids = new Gee.HashSet<string> ();
+      var local_ids = new SmallSet<string> ();
 
       foreach (var persona in personas)
         {
@@ -2178,7 +2180,7 @@ public class Folks.IndividualAggregator : Object
        * In the worst case, this will double the number of personas, since if
        * none of the personas have anti-links writeable, each will have to be
        * linked with a new writeable persona. */
-      var individual_personas = new HashSet<Persona> (); /* as we modify it */
+      var individual_personas = new SmallSet<Persona> (); /* as we modify it */
       individual_personas.add_all (individual.personas);
 
       debug ("    Inserting anti-links:");
@@ -2186,7 +2188,7 @@ public class Folks.IndividualAggregator : Object
         {
           try
             {
-              var personas = new HashSet<Persona> ();
+              var personas = new SmallSet<Persona> ();
               personas.add (pers);
               debug ("        Anti-linking persona '%s' (%p)", pers.uid, pers);
 
@@ -2197,7 +2199,7 @@ public class Folks.IndividualAggregator : Object
                   writeable_persona.uid, writeable_persona);
 
               /* Make sure not to anti-link the new persona to pers. */
-              var anti_link_personas = new HashSet<Persona> ();
+              var anti_link_personas = new SmallSet<Persona> ();
               anti_link_personas.add_all (individual_personas);
               anti_link_personas.remove (pers);
 
diff --git a/folks/individual.vala b/folks/individual.vala
index ac373e02..1362b451 100644
--- a/folks/individual.vala
+++ b/folks/individual.vala
@@ -103,8 +103,7 @@ public class Folks.Individual : Object,
     WebServiceDetails
 {
   /* Stores the Personas contained in this Individual. */
-  private HashSet<Persona> _persona_set =
-      new HashSet<Persona> ();
+  private SmallSet<Persona> _persona_set = new SmallSet<Persona> ();
   /* Read-only view of the above set */
   private Set<Persona> _persona_set_ro;
   /* Mapping from PersonaStore -> number of Personas from that store contained
@@ -495,7 +494,7 @@ public class Folks.Individual : Object,
       set { this.change_gender.begin (value); } /* not writeable */
     }
 
-  private HashSet<UrlFieldDetails>? _urls = null;
+  private SmallSet<UrlFieldDetails>? _urls = null;
   private Set<UrlFieldDetails>? _urls_ro = null;
 
   /**
@@ -512,7 +511,7 @@ public class Folks.Individual : Object,
       set { this.change_urls.begin (value); } /* not writeable */
     }
 
-  private HashSet<PhoneFieldDetails>? _phone_numbers = null;
+  private SmallSet<PhoneFieldDetails>? _phone_numbers = null;
   private Set<PhoneFieldDetails>? _phone_numbers_ro = null;
 
   /**
@@ -529,7 +528,7 @@ public class Folks.Individual : Object,
       set { this.change_phone_numbers.begin (value); } /* not writeable */
     }
 
-  private HashSet<EmailFieldDetails>? _email_addresses = null;
+  private SmallSet<EmailFieldDetails>? _email_addresses = null;
   private Set<EmailFieldDetails>? _email_addresses_ro = null;
 
   /**
@@ -546,7 +545,7 @@ public class Folks.Individual : Object,
       set { this.change_email_addresses.begin (value); } /* not writeable */
     }
 
-  private HashSet<RoleFieldDetails>? _roles = null;
+  private SmallSet<RoleFieldDetails>? _roles = null;
   private Set<RoleFieldDetails>? _roles_ro = null;
 
   /**
@@ -563,7 +562,7 @@ public class Folks.Individual : Object,
       set { this.change_roles.begin (value); } /* not writeable */
     }
 
-  private HashSet<string>? _local_ids = null;
+  private SmallSet<string>? _local_ids = null;
   private Set<string>? _local_ids_ro = null;
 
   /**
@@ -615,7 +614,7 @@ public class Folks.Individual : Object,
       set { this.change_calendar_event_id.begin (value); } /* not writeable */
     }
 
-  private HashSet<NoteFieldDetails>? _notes = null;
+  private SmallSet<NoteFieldDetails>? _notes = null;
   private Set<NoteFieldDetails>? _notes_ro = null;
 
   /**
@@ -632,7 +631,7 @@ public class Folks.Individual : Object,
       set { this.change_notes.begin (value); } /* not writeable */
     }
 
-  private HashSet<PostalAddressFieldDetails>? _postal_addresses = null;
+  private SmallSet<PostalAddressFieldDetails>? _postal_addresses = null;
   private Set<PostalAddressFieldDetails>? _postal_addresses_ro = null;
 
   /**
@@ -735,7 +734,7 @@ public class Folks.Individual : Object,
         }
     }
 
-  private HashSet<string>? _groups = null;
+  private SmallSet<string>? _groups = null;
   private Set<string>? _groups_ro = null;
 
   /**
@@ -1201,11 +1200,11 @@ public class Folks.Individual : Object,
         }
       else if (added == null)
         {
-          _added = new HashSet<Persona> ();
+          _added = SmallSet.empty<Persona> ();
         }
       else if (removed == null)
         {
-          _removed = new HashSet<Persona> ();
+          _removed = SmallSet.empty<Persona> ();
         }
 
       // We've now guaranteed that both _added and _removed are non-null.
@@ -1215,7 +1214,7 @@ public class Folks.Individual : Object,
 
   private void _store_removed_cb (PersonaStore store)
     {
-      var remaining_personas = new HashSet<Persona> ();
+      var remaining_personas = new SmallSet<Persona> ();
 
       /* Build a set of the remaining personas (those which weren't in the
        * removed store. */
@@ -1237,7 +1236,7 @@ public class Folks.Individual : Object,
       Persona? actor,
       GroupDetails.ChangeReason reason)
     {
-      var remaining_personas = new HashSet<Persona> ();
+      var remaining_personas = new SmallSet<Persona> ();
 
       /* Build a set of the remaining personas (those which aren't in the
        * set of removed personas). */
@@ -1512,7 +1511,7 @@ public class Folks.Individual : Object,
       /* Lazily instantiate the set of groups. */
       else if (this._groups == null)
         {
-          this._groups = new HashSet<string> ();
+          this._groups = new SmallSet<string> ();
           this._groups_ro = this._groups.read_only_view;
           created = true;
         }
@@ -1521,7 +1520,7 @@ public class Folks.Individual : Object,
       if (!created && !force_update)
          return;
 
-      var new_groups = new HashSet<string> ();
+      var new_groups = new SmallSet<string> ();
 
       /* FIXME: this should partition the personas by store (maybe we should
        * keep that mapping in general in this class), and execute
@@ -2063,14 +2062,14 @@ public class Folks.Individual : Object,
           () => { return this._urls == null; },
           () =>
             {
-              this._urls = new HashSet<UrlFieldDetails> (
+              this._urls = new SmallSet<UrlFieldDetails> (
                   AbstractFieldDetails<string>.hash_static,
                   AbstractFieldDetails<string>.equal_static);
               this._urls_ro = this._urls.read_only_view;
             },
           () =>
             {
-              var new_urls = new HashSet<UrlFieldDetails> (
+              var new_urls = new SmallSet<UrlFieldDetails> (
                   AbstractFieldDetails<string>.hash_static,
                   AbstractFieldDetails<string>.equal_static);
               var urls_set = new HashMap<unowned string,
@@ -2121,14 +2120,14 @@ public class Folks.Individual : Object,
           () => { return this._phone_numbers == null; },
           () =>
             {
-              this._phone_numbers = new HashSet<PhoneFieldDetails> (
+              this._phone_numbers = new SmallSet<PhoneFieldDetails> (
                   AbstractFieldDetails<string>.hash_static,
                   AbstractFieldDetails<string>.equal_static);
               this._phone_numbers_ro = this._phone_numbers.read_only_view;
             },
           () =>
             {
-              var new_phone_numbers = new HashSet<PhoneFieldDetails> (
+              var new_phone_numbers = new SmallSet<PhoneFieldDetails> (
                   AbstractFieldDetails<string>.hash_static,
                   AbstractFieldDetails<string>.equal_static);
               var phone_numbers_set = new HashMap<string, PhoneFieldDetails> (
@@ -2178,14 +2177,14 @@ public class Folks.Individual : Object,
           create_if_not_exist, () => { return this._email_addresses == null; },
           () =>
             {
-              this._email_addresses = new HashSet<EmailFieldDetails> (
+              this._email_addresses = new SmallSet<EmailFieldDetails> (
                   AbstractFieldDetails<string>.hash_static,
                   AbstractFieldDetails<string>.equal_static);
               this._email_addresses_ro = this._email_addresses.read_only_view;
             },
           () =>
             {
-              var new_email_addresses = new HashSet<EmailFieldDetails> (
+              var new_email_addresses = new SmallSet<EmailFieldDetails> (
                   AbstractFieldDetails<string>.hash_static,
                   AbstractFieldDetails<string>.equal_static);
               var emails_set = new HashMap<string, EmailFieldDetails> (
@@ -2236,14 +2235,14 @@ public class Folks.Individual : Object,
           () => { return this._roles == null; },
           () =>
             {
-              this._roles = new HashSet<RoleFieldDetails> (
+              this._roles = new SmallSet<RoleFieldDetails> (
                   AbstractFieldDetails<Role>.hash_static,
                   AbstractFieldDetails<Role>.equal_static);
               this._roles_ro = this._roles.read_only_view;
             },
           () =>
             {
-              var new_roles = new HashSet<RoleFieldDetails> (
+              var new_roles = new SmallSet<RoleFieldDetails> (
                   AbstractFieldDetails<Role>.hash_static,
                   AbstractFieldDetails<Role>.equal_static);
 
@@ -2276,12 +2275,12 @@ public class Folks.Individual : Object,
           () => { return this._local_ids == null; },
           () =>
             {
-              this._local_ids = new HashSet<string> ();
+              this._local_ids = new SmallSet<string> ();
               this._local_ids_ro = this._local_ids.read_only_view;
             },
           () =>
             {
-              var new_local_ids = new HashSet<string> ();
+              var new_local_ids = new SmallSet<string> ();
 
               foreach (var persona in this._persona_set)
                 {
@@ -2341,7 +2340,7 @@ public class Folks.Individual : Object,
           create_if_not_exist, () => { return this._postal_addresses == null; },
           () =>
             {
-              this._postal_addresses = new HashSet<PostalAddressFieldDetails> (
+              this._postal_addresses = new SmallSet<PostalAddressFieldDetails> (
                   AbstractFieldDetails<PostalAddress>.hash_static,
                   AbstractFieldDetails<PostalAddress>.equal_static);
               this._postal_addresses_ro = this._postal_addresses.read_only_view;
@@ -2349,7 +2348,7 @@ public class Folks.Individual : Object,
           () =>
             {
               var new_postal_addresses =
-                  new HashSet<PostalAddressFieldDetails> (
+                  new SmallSet<PostalAddressFieldDetails> (
                       AbstractFieldDetails<PostalAddress>.hash_static,
                       AbstractFieldDetails<PostalAddress>.equal_static);
 
@@ -2437,14 +2436,14 @@ public class Folks.Individual : Object,
           () => { return this._notes == null; },
           () =>
             {
-              this._notes = new HashSet<NoteFieldDetails> (
+              this._notes = new SmallSet<NoteFieldDetails> (
                   AbstractFieldDetails<string>.hash_static,
                   AbstractFieldDetails<string>.equal_static);
               this._notes_ro = this._notes.read_only_view;
             },
           () =>
             {
-              var new_notes = new HashSet<NoteFieldDetails> (
+              var new_notes = new SmallSet<NoteFieldDetails> (
                   AbstractFieldDetails<string>.hash_static,
                   AbstractFieldDetails<string>.equal_static);
 
@@ -2476,8 +2475,8 @@ public class Folks.Individual : Object,
     {
       assert (replacement_individual == null || replacement_individual != this);
 
-      var added = new HashSet<Persona> ();
-      var removed = new HashSet<Persona> ();
+      var added = new SmallSet<Persona> ();
+      var removed = new SmallSet<Persona> ();
 
       /* Determine which Personas have been added. If personas == null, we
        * assume it's an empty set. */
diff --git a/folks/potential-match.vala b/folks/potential-match.vala
index 6e7bb405..21482698 100644
--- a/folks/potential-match.vala
+++ b/folks/potential-match.vala
@@ -101,8 +101,7 @@ public class Folks.PotentialMatch : Object
    *
    * @since 0.5.1
    */
-  public static Set<string> known_email_aliases =
-      new Gee.HashSet<string> ();
+  public static Set<string> known_email_aliases = new SmallSet<string> ();
 
   private static double _DIST_THRESHOLD = 0.70;
   private const string _SEPARATORS = "._-+";