Unfortunately, we have to do a linear pass when inserting a new (field_id, field_offset) tuple to overwrite duplicates (same field_id, different field_offset).

It is linear because there is no guarantee that the elements are ordered by field_id. That guarantee only lives in MetadataBuilder.fields.

This is now outdated, upsert_field is O(1) by making use of a mapping from field_id to the index position in fields.

I think you could store a &str here avoiding a to_string() (allocation) in the hot loop.

You could use a hashmap with ahash as hasher, getting some more speed.

I need to profile this to confirm, but I suspect a non trivial amount of the benchmark time isspent actually generating the random strings

To ensure we are only benchmarking the VariantBuilder, I suggest pre-generating a string table and then pick from them quasi-randomly -- something like

// make a table with 117 random strings (so it doesn't evenly divide into 25000)
let strings = (0..117).map(|_| random_string(&mut rng).collect::<Vec<_>>();
...
        b.iter(|| {
          let mut current_string = 0;
...
           object_builder.insert("name", &strings[current_string]);
           current_string = (current_string + 1) % strings.len();
..

Likewise for the other bencmarks

Here is a profile. There is evidence of a non trivial amount of time spent in random creation (and I think a bunch of the allocation / free shown is related to creating Strings as well)

You might be able to use an IndexSet here to store the field_ids as well as preserving order

I should've recognized that! That's very exciting.

To be clear I was thinking you could use a single hash set (instead of a map + vec)

    field_id_to_index: IndexSet<u32>, // (field_id, insert order corresponds to field offset)

Hm, I'm a bit confused. An IndexSet<u32> is keeping track of the field ids in insert order. Where would we store the respective field offsets?

Would it work to do an IndexMap<u32, u32>, where the key is the field id and the value is the field offset?

Thank you @scovich, I just pushed up a change and it proves to be a nice improvement.

I think it makes sense to remove this test as it is basically testing the internal structure / invariants of the builders. I think it makes more sense to test the public APIs 👍

What could cause the max id to be different from fields.len()-1?

We have no guarantee that fields is sorted in order of field_id, only insertion order. You could imagine creating an object list where the first object is defined with field names a, b, but the second object is defined in the opposite order.

Here are some cases where max_id isn't necessarily the last element in fields. The examples below would still work by taking the last element, but you could imagine defining 255+ keys and an object has the field ids: [258, 1]. Basing the integer width off the last field id would not be ideal here.

  #[test]
  fn nested() {
      let mut variant = VariantBuilder::new();

      let mut obj1 = variant.new_object();

      obj1.insert("c", false);
      obj1.insert("b", false);

      {
          let mut inner_obj = obj1.new_object("a");
          inner_obj.insert("a", false);
          inner_obj.insert("b", false);

          // Here, the nested object's `field` ids are laid out as [2, 1]
          dbg!(inner_obj.fields.iter().map(|(&i, _)| i).collect::<Vec<_>>());
          inner_obj.finish();
      }

      obj1.finish();
  }

  #[test]
  fn predefined_field_names() {
      let mut variant = VariantBuilder::new().with_field_names(&["a", "b", "c", "d", "e"]);

      let mut obj1 = variant.new_object();

      obj1.insert("e", false);
      obj1.insert("a", false);

      // [4, 0]
      dbg!(obj1.fields.iter().map(|(&i, _)| i).collect::<Vec<_>>());

      obj1.finish();
  }

If we want to avoid the linear scan, we can keep a field in ObjectBuilder that keeps track of the largest field id upon every insert.