set field of CleverDict

[blegat]

Looking at the code of CleverDict, set is simply eachindex(vector) isn't it ?
I thought that when an index was deleted, set was updated but it seems we switch to Dict instead so we should either remove this set vector or decide to stay dense when an element is deleted.

[odow]

Can you elaborate?

MathOptInterface.jl/src/Utilities/CleverDicts.jl

Lines 219 to 241 in 22240f0

	function _rehash(c::CleverDict{K}) where {K}
	sizehint!(c.dict, length(c.vector))
	@assert _is_dense(c)
	# Since c is currently dense, iterator protocol from CleverDict is used.
	for (k, v) in c
	c.dict[k] = v
	end
	empty!(c.vector)
	empty!(c.set)
	c.is_dense = false
	return
	end
	function Base.delete!(c::CleverDict{K}, k::K) where {K}
	if _is_dense(c)
	_rehash(c)
	end
	delete!(c.dict, k)
	if !isempty(c.vector)
	empty!(c.vector)
	end
	return
	end

[blegat]

So we should have something like

function Base.delete!(c::CleverDict{K}, k::K) where {K} 
     if _is_dense(c) 
         delete!(c.set, c.hash(k))
     else
         delete!(c.dict, k) 
     end 
     return 
 end 

The switch from dense to dict would only occur if you add out of sequence, not at deletion

[odow]

Isn't that just moving the problem somewhere else?

[blegat]

The field is coming from DenseDict which has this feature and was merged into CleverDict in #1142. If we remove set then what remains of DenseDict ? I guess we had use cases for DenseDict that would rather have a BitSet than a Dict

[odow]

Ah. Yes all for removing .set then. I don't see any obvious reason that it is used for.

[joaquimg]

.set is very to keep functionality from dense dict.
We have uses cases where ordered indexing is very important, for instance in copy.
We can add deletion functionality to .set indeed. I did not because the problem had no shown up at the time. Only addition was being tested, hence I switched to dict in case of deletion for simplicity.

[joaquimg]

Also, since we are looking into performance. There might be a difference between dense and dense+contiguous.
This might lead to 3 modes, which can pay off if its simple enough.
Most use cases do not involve deletions, so having them extremely high performance would be important in such a basic operation.
A first deletion would switch from pure vector to vector+set and out of order addition would switch to dict.

[blegat]

Yes, I am also wondering whether this 3rd mode would make sense.
There is yet another mode: Identity mode in case the key type and value types are the same and all the mapping added yet are identity. You switch to dense the first time it is not identity

[odow]

.set is very to keep functionality from dense dict.

Which functionality, specifically? There's iterating, but there's no reason we couldn't iterate along the vector?

I'll also say: I'm not in favor of adding yet more complexity.

[joaquimg]

Ok, maybe for now .set is not essential since we can iterate in a vector. I would say +1 for simplifying.

However, I would advocate that complexity should be added if it improves benchmarks meaningfully, as long as we can keep it transparent outside CleverDict. In other words, if we have benchmarks for which .set can be better used as @blegat said, I'd say we do it.

These dict operations are bottlenecks very frequently.

I also like identity mode. Happens a lot in copies. Might be a little tricky to preserve operations like iterating in the elements or checking if an element is there (.set could solve this).

[blegat]

Yes, I agree for an identity mode. This should be used most of the times now, even constraint indices are 1 to n now with VectorOfConstraints.
Creating the IndexMap is a significant part of the time in #1287

[odow]

Okay. I looked into this issue. .set is needed if you initialize the CleverDict with space, but then only partially fill it before querying.

@joaquimg do we have a benchmark where resizing the vector if you add one-by-one is a bottleneck? Alternatively, we could just close this issue.

[joaquimg]

I don't have one now.
I have a plan to run a few benchmarks in the following weeks.
We can close this for now and maybe open other ones like the identity mapping @blegat commented.

[blegat]

Yes, let's close this one once we have opened the other ones