Thank you and one question/suggestion

[didiersmets]

Bonjour Patrick et félicitations pour ce précieux travail!

I have a question/suggestion regarding the _get_at method (it came in in the
context of an OA dict - that function is not listed for dict containers in the
readme.md but is it present in m-dict.h and listed in Container.ods).

In Container.ods it is listed as a GET SET KEY method. My understanding of the
present implementation in m-dict.h is that it is instead a "GET OR INIT" method.

The case I have in mind is the situation where one wants to perform an
"insert_or_update" action with only one hashing (thus avoiding a _get
followed by a _set_at).
I presume one classical way to do it is through a f(dict, key, value) where f

• inserts (key, value) if key was not already present, and then returns NULL,
• performs no action but returns a valid pointer to the existing orig_value if the key was present.
  If the returned pointer is not NULL, one does the appropriate update of the orig_value by
  de-referencing it.

My question is : Is the _get_at function [for dict] the relevant function inside mlib for such a use case ? or
did I missed another one ? (since it always returns a valid pointer one needs to circumvent the ambiguity if
either a) the key was already present with an associated value being equal to the init value of
valuetype, and b) the key was not present).

Thank you!
Didier

[Side note: by curiosity I tested mlib for a pure C implementation of the k-nucleotide benchmark game, it was on
par with the one being ranked first and based on gnu pb_ds.]

[P-p-H-d]

Hi Didier,

Thank you for your feedback! I am glad that you like this library.

Regarding your question, the _get_at method is indeed a get existing entry or create a new one method.
If the entry is found, it returns it. Otherwise it creates a new one using the _init method and returns it.
It is indeed not documented for dict which is an error.

For an "insert or update" action, this method is quite useful and simplify the design. You need t call _get_at method and then update the returned entry. Here is an example with an associative array of int -->int:

int *p = dict_int_get_at(dict, 45);
p ++;

This works since the _init method of an int initializes the object to 0.

By the way, did you try your own implementation of the k-nucleotide benchmark or the one from https://github.com/P-p-H-d/mlib/tree/master/bench/nucleotide ?

[P-p-H-d]

I will do something like this by overloading the INIT operator:

#define int_init(d) (d) = 1
DICT_DEF2(dict_int,
          int, M_OPL_int(),
          int, M_OPEXTEND(M_OPL_int(), INIT(int_init)))

void f(dict_int_t dict, int key)
{
  *dict_int_get_at(dict, key) ^= 1;
}

[didiersmets]

By the way, did you try your own implementation of the k-nucleotide benchmark or the one from https://github.com/P-p-H-d/mlib/tree/master/bench/nucleotide ?
Oh this is funny, no I did not know you implemented it as well. I will have a look at yours. I followed rather closely the C++ #2 implementation (the important factor is the way the work is shared between threads, some earlier implementations were dividing the buffer into equal pieces between threads, in C++ #2 they form an advancing front in the buffer which must be more cache friendly). As the hash table is concerned, I first used a baby non generic OA implementation of mine (with no deletion implemented...no need here but cheating so out of the game rules :-). The trivial identity hash seemed kind of optimal speed wise in this specific case. I then tried with mlib dict (with OA and default hash strategy), it was only a couple line changes (which is a very good point for mlib!).

[didiersmets]

Overloading INIT : I agree but it wouldn't be my favorite. If a second counter must start at 1 instead of 0, then should I need another type.
Anyway these are academic examples and there is indeed always ways to circumvent 'difficulties' but I was rather interested to know if there was special reason/need why you did not opt for the return NULL way.

[P-p-H-d]

If a second counter must start at 1 instead of 0, then should I need another type.

I would say yes in general. But I can imagine some scenario where it won't be a good idea.

Anyway these are academic examples and there is indeed always ways to circumvent 'difficulties' but I was rather interested to know if there was special reason/need why you did not opt for the return NULL way.

You can perfectly use the return NULL way (with the _get method &_set_at). I think both approach should run at mostly the same speed: I have found that the compiler is usually able to optimize and extract the common part between the _get function and the _set_at function so that only one hash access is performed.
The only reason I slightly prefer _get_at is from an academic point of view: returning null if it is not found puts more code on the user and more chance to write incorrect code.

[didiersmets]

Thank you. I just tested your (impressive) implementation of k-nucleotide. In the critical loop at line 109-114 and 121-126 you use the _get followed by set_at exactly as in my tiny example above. I was tempted to replace in your code each of these blocks by the one line equivalent using _get_at :
uint32_t *p = dict_oligonucleotide_get_at(hash, key); (*p) ++;
(it is a case where it works straight without touching INIT, and looks appealing at first with only one call and no branching).
BUT your initial code is not slower, it is actually slightly faster ! (in O3, in O0 or O1 it is inverted as expected, still). So you are perfectly correct, gcc does a better job at optimizing "clearer" code as yours. Very informative and fully convinced. Thanks!