Hashmap fixes

Adds functionality to grow a hashmap, can be used to pre-allocate elements when the final size is known.

Fixes overflows on re-hashing, although I'm not too sure how to test this in practice.

Implements #587 (closed).

Isn't it more efficient to set a larger initial size when using the table in the FOF code?

Yes, but I want to keep the API as general as possible. The way I would expect it to be used is

hashmap_t map;
hashmap_init(&map);
hashmap_grow(&map, 2 * num_parts);

Growing the empty hashmap has pretty much zero cost.

Right. But that call is not made yet in the FOF code. Should I add it?

Ah, yes, please do!

I left it out of this MR because I don't really know where we would need how much.

Yeah me neither.

/*new_size=*/0 ?

Looking through the FOF code it seems hard to come up with an educated guess about the sizes of either of the two maps we use.

Could we nevertheless start them with a generic size of 1000 or so? That will basically cost nothing memory-wise but will make us skip the initial growth phase.

I ran the EAGLE-25 on 32 MPI ranks triggering FOF every 500 steps in 10 separate runs and they all completed succesfully. I think this is all fine.

Maybe @pdraper has other tests to suggest?

assigned to @pdraper

to be safe, could you add a debug message to make sure the overflow actually happens?

I did:

diff --git a/src/hashmap.c b/src/hashmap.c
index 3ebf927..e8fc11f 100644
--- a/src/hashmap.c
+++ b/src/hashmap.c
@@ -309,6 +309,9 @@ void hashmap_grow(hashmap_t *m, size_t new_size) {
              If this happens, store the offending element in the strays buffer
              for now. */
           else {
+
+           message("HASHMAP OVERFLOW");
+
             /* (Re)allocate strays buffer? */
             if (strays_count == strays_size) {
               hashmap_element_t *temp_buff;
@@ -338,10 +341,15 @@ void hashmap_grow(hashmap_t *m, size_t new_size) {
   /* If we have any strays, add them back to the hashmap. This will inevitably
      trigger a rehashing, but that's not our problem. */
   if (strays_count) {
+
+    message("HASHMAP STRAY ELIMINATION");
+
     for (size_t k = 0; k < strays_count; k++) {
       hashmap_put(m, strays[k].key, strays[k].value);
     }
     swift_free("hashmap_strays", strays);
+
+    message("HASHMAP DEALT WITH ALL STRAYS");
   }
 }

It happened twice in all my runs. We survived in both cases.

I had a development branch that I thought tripped over this problem more frequently, but that doesn't seem to happen now! Since you've managed anyway, all looks good to go I guess.

All good for me unless @nnrw56 wants to pick up on my suggestion above to initialise the hash maps to 1000 or so.

changed the description

changed milestone to %Paris

Any last words on this from anyone?

merged

mentioned in commit a3c1cc83