Memory indexes

Question

I have a session concept that stores objects in different states.

Sometimes I need to scan a session for objects matching a specific request, but I do it a lot, and performance testing has shown that it becomes a bottleneck in some areas.

Therefore, I would like to introduce the concept of indexes in a session.

Something like...

public IDictionary<K, V> GetIndex<K, V>(Func<V, K> keySelector) 

However, I'm not sure how to test Func “equality” like this. Obviously, I want the index to be built only on the first call to GetIndex and subsequent calls, so as not to build it again.

How should I display them inside in order to search for the existence of an index?

 IDictionary<???, IDictionary<K, V>> indexes = ... 

Basically, how should I store ???. Maybe I can't do it with Func, but maybe there is another way.

Answer 1

The simplest approach is probably to calculate the hash of the query and insert the results into the dictionary using the hash as the key.

If your queries are strings, perhaps you can just use the string.GetHashCode function to compute a simple hash for the string data. If your queries are Linq queries, then GetHashCode may not work unless Linq specifically overrides this method to calculate the hash over the expression tree instead of the default instance pointer. By default, the .GetHashCode implementation simply returns the value obtained from the identifier of the object instance in memory, without regard to the contents of the object data.

If your queries are strings and fairly uniform / consistent in construction, the calculation of a simple hash of the string should be sufficient to reduce query traffic using the cache. If your requests are less consistent in the structure (for example, equivalent requests, but with arguments in a different order, for example), you may need to create your own hash function that calculates the hash in the canonized form of the input request to improve cache hit rates for requests that are logically equivalent, but text different.

As your hash calculations become more expensive, they will decrease cache utilization. Make sure the query operation is expensive enough to justify the time spent computing the hash memory and consuming memory for the cache to provide net savings in execution time. The request operation must be at least 2 or more orders of magnitude greater than the overhead of cache and cache management. If your request operation is not related to a process or internetwork call, your cache overhead will almost certainly be overshadowed by the cost of the request.

Answer 2

You can use Expression<Func<K,V>> and then Compile() expression when you need to execute.

To check for equality, take a look at this SO question:
How to check if two expressions Expression <Func <t, bool → are the same

Alternatively, you can specify name indexes and continue using the delegate:

 public IDictionary<K, V> GetIndex<K, V>(string indexName, Func<V, K> keySelector) IDictionary<string, IDictionary<K, V>> indexes = .. 

Answer 3

Comparing expressions in loops can be more time consuming than choosing from a dictionary. As already indicated in the thread, there are ways to compare them, but very time-consuming and inaccurate:

 x => x.Key == 1 

against

 y => y.Key == 1 

against

 int value = 1 x => x.Key == value 

will give false

So creating ad hoc indexes is not a good solution.

What you can do is to have an Indexing factory class with predefined expression patterns that create expressions when you first call some combination of parameters and use them (instances) with .Equals by reference.

Something like (pseudo # ode):

 static class Indexfactory { private static Dictionary<IndexcreationParams,Expression> ... // more of these as required public static Expression getIndex<Tret,P1,P2,P3,...>(IndexType type, P1 p1,P2 p2,P3 p3...) { // create expression from template with the supplied parameters // if not already existent, else rerturn it from static storage // store expression in some private storage } } 

Then save the expression as a key in the dictionary with the list of results when it is executed first. In the next executions, check if you have cached results for this expression, since if you use factory, you will always get the same link.