* Peng Zhang [off-list ref] [230818 05:40]:

在 2023/8/17 01:40, Liam R. Howlett 写道:

quoted

* Peng Zhang [off-list ref] [230816 09:11]:

quoted

在 2023/8/1 00:48, Liam R. Howlett 写道:

quoted

* Peng Zhang [off-list ref] [230731 08:39]:

quoted

在 2023/7/27 00:08, Liam R. Howlett 写道:

quoted

* Peng Zhang [off-list ref] [230726 04:10]:

quoted

If mas has located a specific entry, it may be need to replace this
entry, so introduce mas_replace_entry() to do this. mas_replace_entry()
will be more efficient than mas_store*() because it doesn't do many
unnecessary checks.

This function should be inline, but more functions need to be moved to
the header file, so I didn't do it for the time being.

I am really nervous having no checks here.  I get that this could be
used for duplicating the tree more efficiently, but having a function
that just swaps a value in is very dangerous - especially since it is
decoupled from the tree duplication code.

I've thought about this, and I feel like this is something the user
should be guaranteed. If the user is not sure whether to use it,
mas_store() can be used instead.

Documentation often isn't up to date and even more rarely read.
mas_replace_entry() does not give a hint of a requirement for a specific
state to the mas.  This is not acceptable.

The description of the function also doesn't say anything about a
requirement of the maple state, just that it replaces an already
existing entry.  You have to read the notes to find out that 'mas must
already locate an existing entry'.

quoted

And we should provide this interface
because it has better performance.

How much better is the performance?  There's always a trade off but
without numbers, this is hard to justify.

I have implemented a new version of this pachset, and I will post it
soon.

I tested the benefits of mas_replace_entry() in userspace.
The test code is attached at the end.

Run three times:
mas_replace_entry(): 2.7613050s 2.7120030s 2.7274200s
mas_store():         3.8451260s 3.8113200s 3.9334160s

This runtime is too short, we should increase the number of elements or
loops until it is over 10 seconds.  This will make the setup time
and other variances less significant and we can use the command run time
as a rough estimate of performance. IIRC 134 was picked for a rough
estimate of an average task size so maybe increase the loops.

I changed nr_entries to 1000, and the measured numbers are as follows:
mas_replace_entry():	20.0375820s
mas_store():		28.6175720s
It can be seen that mas_store() is still nearly 40% slower.

To be clear, I didn't doubt your numbers or want you to rerun the
benchmark.  I was just saying we should increase the loops now that the
tree is faster.  It should allow for you to not need to use clock count
to see benefits - although they will always be more accurate.

Thanks,
Liam