John Cowan <xxxxxx@mercury.ccil.org> writes:

> Taylan Ulrich Bayırlı/Kammer scripsit:
>
>> it's bad to expose any operations with nondeterministic order
>> of applications/results.
>
> As long as -keys is non-deterministic, I think everything else is just
> beating the air.  In any case, nobody is going to randomize the order:
> it is in fact deterministic for any particular set of keys, it's just
> that the ordering you get is complicated enough that users treat it
> as unpredictable.

I see a couple ways in which one could call them nondeterministic.

- A trivial change to the program input (say, one more or one less datum
  to be inserted into a table) can overhaul the order in the table at a
  point in the program where one of the whole-table operations is used.

- Same thing except with the code changing instead of the input.

- Using one of the whole-table operations, then a single delete
  operation, then another whole-table operation, can give you totally
  different orders in the two uses of the whole-table operation, because
  a compaction happened in between.

- The last point combined with the other two points: on one run of your
  program the two whole-table operations *do* have the same order, in
  another run they don't.

It really has good Heisenbug potential.  People should absolutely never
rely on the order in any way if they want to make sure there's no loaded
guns pointing at their feet.

>> Radical solutions involve 1. dropping such operations entirely or
>> keeping them very minimal, 2. specifying ordered hash tables like in
>> PyPy.
>
> The latter would be a fine idea, actually, based on what I've read.

For now I think we should stick to something which implementations can
support easily on top of their existing low-level hash table code.

Taylan