Re: [PATCH] *-map, *-omap: Allow passing NULL to search

[Bruno Haible]

Hi Colin,

> It's sometimes convenient to have a map whose values may be NULL, but in
> that case it's a little awkward to determine whether a key exists in the
> map: gl_map_get returns NULL for both "key not found" and "value is
> NULL", so one needs a local variable just for the purpose of passing its
> address to gl_map_search.

Yes. You can consider it "a little awkward", and you can get away with it
through an inline function like this:

static bool
gl_map_entry_exists (gl_map_t map, const void *key)
{
  const void *value;
  return gl_map_search (map, key, &value);
}

> Instead, allow the return pointers to be NULL, so that one can use
> gl_map_search (map, NULL, NULL) to check existence.

What you propose is MORE awkward, for two reasons:

  1) For this code, performance is relevant.

     On modern processors, conditional jumps are significantly more
     costly than a simple instruction on values and addresses in the
     cache. (Something like between 5 and 20 cycles, when a single
     elementary arithmetic or load/store instruction is 1 cycle.)
     Why? Because modern processors are pipelined, and a conditional jump
     stalls the pipeline. Or, in processors which have speculative execution,
     when there are more conditional jumps, the speculative execution
     depth is obviously reduced.
     So, allocating a variable on the stack, filling it, and then ignoring
     its value is FASTER than a conditional jump whose effect is to save
     1 store instruction.

     You'll also notice that this is why I wrote

       GL_MAP_INLINE const void *
       gl_map_get (gl_map_t map, const void *key)
       {
         const void *value = NULL;
         gl_map_search (map, key, &value);
         return value;
       }

     and not

       GL_MAP_INLINE const void *
       gl_map_get (gl_map_t map, const void *key)
       {
         const void *value;
         if (gl_map_search (map, key, &value)
           return value;
         else
           return NULL;
       }

  2) Allowing NULL pointers as arguments in all possible places is
     *not* a good coding style in general. (It may be a good practice,
     though, when you're being paid for a consulting project and your
     code will never be maintained once you have delivered it.)
     A large portion of these NULL checks is redundant; it clutters
     up the code and triggers conditional jumps. Additionally, it
     increases the burden of unit-testing the code.

It can be discussed whether the public API gl_map.h and gl_omap.h
should include functions like gl_map_entry_exists. Some people (like
the GNOME glib authors) attempt to provide all possible variants that
might some day be useful. Whereas I chose to provide a set of functions
that is not so large, and omit functions that can be implemented by the
user in a straightforward way. (gl_map_get is a notable exception to
this rule.) gl_map_entry_exists is clearly part of those functions
that users can implement themselves.

Bruno