1

I have a dictionary in the form of Dictionary<int, List<int>>

The problem is that I need to group the keys together into buckets defined by the value (List<int>). It is easier to explain with an example.

Consider the dictionary:

{
    1: [5,4]
    2: [4]
    3: [10]
}

Out of this, I need the dictionary:

{
    5: [1]
    4: [2, 1]
    10: [3]
}

The approach I took for this is to basically flatten the input dictionary, producing many key value pairs

 1: 5
 1: 4
 2: 4
 3: 10

And then grouping on the value (getting the correct result.)

The problem with this approach is that it takes a long time, and I cannot parallelize it.

The LINQ query I wrote for this is:

Dictionary<int, List<int>> test = <Some init data set>;
test.SelectMany(x => x.Value.Select(y => Tuple.Create(x.Key, y)))
 .GroupBy(x=>x.Item2).ToDictionary(x=>x.Key, x=>x.ToList());

Is there a better / more efficient way to do this? My concern is that by flattening the list in the value operand, I am creating a lot of records, and therefore this algorithm will probably not scale very well?

Thanks!

EDIT:

More information:

Here is some background information about the problem as a whole.

The dictionary is actually a def-use chain; where the key is a reference to a statement that define some data, and the value is a list of references to statements use the data produced by the statement from this definition. Since the code that this optimizer works with is obfuscated, the def-use chain is unusually large (ie, not consistent with what a def-use chain would be on code that someone would normally write.) Therefore, there are an unusual amount of definitions in the def-use chain.

I am trying to build a graph so I can ask: I need this statement here, so what other statements do I also need to carry along with me to keep that statement valid (FWIW, the code is in Static Single Assignment form.)

So to build this graph, I create a Node for each statement in the application. Then I:

  1. Flatten the def-use chain (list of, for each statement that produces data, where is that data used)
  2. group by uses (For each use of produced data, what are the required definitions)
  3. For each use, connect to its respective required definition

Now we essentially have the graph, I can forward traverse at any node to find all statements I need to keep for that node to remain "valid". I used some tricks to make building and traversing the graph very cheap, but #2 is by far the bottle-neck here.

The code that I am working with (ie, statements etc) are purposely crafted to make computations like this not cheap. Ie, this is not normal code written by a person.

Also, this application has a lot of resources to its disposal (many cores 30+, 30GB+ memory.) So really, I am looking for an algorithm that can scale (ie, with a even larger def-use chain.)

13
  • 3
    If N = the sum of the length of all lists in the original dictionary (which is equal to the number of key/value pairs mentioned in your question), you will always need O(N) operations at least to read all elements, and O(N) operations to write them into a new dictionary, regardless of the old and the new order. There is no way around this. – Doc Brown Jul 29 '20 at 20:33
  • 2
    ... Said that, you may gain some speed improvement by replacing your Linq expression by two nested loops (avoiding the tuple creation). But don't expect too much. I can't prove it, but I am pretty sure the creation of the resulting dictionary cannot be parallelized. – Doc Brown Jul 29 '20 at 20:38
  • 2
    I guess the easiest way to find out is by implementing the straightforward solution without Linq, using two nested loops and fill new dictionary incrementally, and then benchmark the speed of both approaches. I guess this would take me less then an hour. – Doc Brown Jul 29 '20 at 20:44
  • 1
    Is the first dictionary a given, or is it something that you create or fill yourself? In the first case, I agree with @DocBrown that there is hardly any room for optimizing the algorithm. In the second case, you can update/insert the values in the second dictionary at the same time when adding values to the first dictionary, which might be far more efficient than looping and sorting afterwards. – Frits Jul 30 '20 at 4:33
  • 1
    With 3million entries, I would rather expect the methods I'm using to parallelise pretty well, since they won't be contending most of the time, but they don't (60seconds with LINQ, 10seconds with serial, 8seconds with 8threads (which end up mostly idling) & a current dictionary). This might suggest the problem is data-access, which isn't going to be solved by parallelism. Indeed, running 2 serials simultaneously takes just as long as running 2 back to back. – VisualMelon Aug 2 '20 at 17:07
1

I can't provide a real explanation for what is going on, but in my rough tests, the only method I can find which parallelises well is one based on a parallel sort. A (fairly simple) version with a concurrent dictionary doesn't perform poorly, but it's not as good. The trick seems to be to simply minimise the number of dictionary lookups, because while we might assume its O(1), it's not perfect and it will be jumping all over the memory and messing with the caching. The sort, on the other hand, will be either QuickSort or MergeSort, both of which spend most of their time looking at things that are near one-another (I hope). The methods that don't parallelise well also don't run well in parallel as separate instances: this suggests it is not any locking/data contention that is slowing them down, but rather they are simply limited by the rate at which my computer can supply them with numbers from widely distributed locations in memory.

The parallel-sorting method is to stuff all the pairs in a list, perform a parallel sort, and then efficiently load that list into a dictionary by scanning through the list: this means that the number of lookups ceases to depend upon the number elements per record, only the number of records.

The test data I am using is a dictionary of up to N records, where each entry has on average 1/µ elements (I tried µ=0.1 and µ=0.01). Note that sorting is O(nm log (nm), so in theory should scale worse than a dictionary based method (~O(nm) assuming a good hash), but for n >= 1M it is significantly faster than all other methods with my randomly generated test data.

All my test code and some (sparse) results can be found in this gist: https://gist.github.com/VisualMelon/0ac1a1fd6e2db1273fb1d49a32d234ce

The 'winning' method is as follows:

public static void Merge<T>(KeyValuePair<T, T>[] a, KeyValuePair<T, T>[] b, KeyValuePair<T, T>[] res) where T : IComparable<T>
{
    int i = 0;
    int j = 0;
    int k = 0;

    while (true)
    {
        var morea = i < a.Length;
        var moreb = j < b.Length;

        if (morea & moreb)
        {
            if (a[i].Key.CompareTo(b[j].Key) > 0)
            {
                res[k++] = b[j++];
            }
            else
            {
                res[k++] = a[i++];
            }
        }
        else if (morea)
        {
            while (i < a.Length)
                res[k++] = a[i++];
        }
        else if (moreb)
        {
            while (j < b.Length)
                res[k++] = b[j++];
        }
        else
        {
            break;
        }
    }
}

public static Dictionary<T, List<T>> ParallelSorts<T>(Dictionary<T, List<T>> data, int threadNumber) where T : IComparable<T>
{
    var kvs = new List<KeyValuePair<T, T>>();
    foreach (var kv in data)
    {
        var k = kv.Key;
        foreach (var v in kv.Value)
        {
            kvs.Add(new KeyValuePair<T, T>(v, k));
        }
    }

    if (kvs.Count == 0)
    {
        return new Dictionary<T, List<T>>();
    }

    int threads = 1 << threadNumber;

    int[] partitions = new int[threads + 1];
    for (int pi = 0; pi < threads; pi++)
    {
        partitions[pi] = (kvs.Count * pi) / threads;
    }
    partitions[threads] = kvs.Count;

    var subLists = new KeyValuePair<T, T>[threads][];

    var tasks = new Action[threads];
    for (int pi = 0; pi < threads; pi++)
    {
        var _pi = pi;
        var sl = subLists[pi] = new KeyValuePair<T, T>[partitions[_pi + 1] - partitions[_pi]];
        tasks[_pi] = () =>
        {
            kvs.CopyTo(partitions[_pi], sl, 0, sl.Length);
            Array.Sort(sl, (a, b) => a.Key.CompareTo(b.Key));
        };
    }
    Parallel.Invoke(tasks);

    for (int stride = 1; stride < threads; stride *= 2)
    {
        tasks = new Action[threads / (stride * 2)];
        for (int pi = 0; pi < threads; pi += stride * 2)
        {
            var a = subLists[pi];
            var b = subLists[pi + stride];
            var res = subLists[pi] = new KeyValuePair<T, T>[a.Length + b.Length];
            subLists[pi + stride] = null;
            tasks[pi / (stride * 2)] = () => Merge(a, b, res);
        }
        Parallel.Invoke(tasks);
    }

    var dictionary = new Dictionary<T, List<T>>();

    var kvs2 = subLists[0];
    var l = new List<T>();
    T lastKey = kvs2[0].Key;
    for (int i = 0; i < kvs2.Length; i++)
    {
        var next = kvs2[i];
        if (next.Key.CompareTo(lastKey) != 0)
        {
            dictionary.Add(lastKey, l);
            lastKey = next.Key;
            l = new List<T>() { next.Value };
        }
        else
        {
            l.Add(next.Value);
        }
    }
    dictionary.Add(lastKey, l);

    return dictionary;
}

No real effort was made to optimise this implementation. It could probably be improved by using a decent parallel sort. The parallel sort here involves sorting even partitions of the data with concurrent calls to Array.Sort, before merging them (partly in parallel for >= 4 threads).

Other methods in the gist include one based on @BionicCode's LINQ, 2 methods based on dictionary merges as described by @Kain0_0, and a 'naive' serial loop (which outperforms all the linq methods), and a couple of others. The only method I would personally consider using for large volumes (apart from the parallel sort) is the one based on a concurrent dictionary: it is really simple and seems to perform well when m is large.

Generally it seems that increasing n makes life worse than increasing m in proportion. This makes sense, because increasing n increases the size of the dictionaries, while increasing m just increases the sizes of the lists.

Of course, my numbers may not generalise to a machine with better RAM, a bigger cache, more cores, on 'real' data, with no other processes running, not on a weekday, even larger n etc. etc. but I thought the numbers were sufficiently interesting that I should write this up. Maybe someone can explain better what is going on (or point out some deficiencies in my tests).

3
  • I don't think sorting is a requirement, this wouldn't generally make much sense. You can improve further by creating unsorted buckets. The algorithm is basically swap key <-> value and flatten the bucket by mapping its items to the common key - create a reverse table. Anyway, nice work with benchmarking different solutions. Although I think the differences are too small to be relevant in the context of the problem. – BionicCode Aug 7 '20 at 20:25
  • @BionicCode I was trying to assume there won't be predictable buckets (i.e. pretend they aren't sequential ints), but it's probably a good idea to try that explicitly. – VisualMelon Aug 7 '20 at 20:31
  • Ah, that's cheating my brother. The actual handicap is the fact that there is no simple value to value mapping. It's a one-to-many or even a many-to-many relation between key and value. That's what's critical for the efficiency of any algorithm. – BionicCode Aug 7 '20 at 20:39
1

You can slightly improve the LINQ performance by using Enumerable.ToLookup or Enumerable.GroupBy instead of Enumerable.ToDictionary.

When you plan to iterate over the grouped result, then using Enumerable.GroupBy offers the best performance, as it offers pure lazy evaluation:

Dictionary<int, List<int>> input = <Some init data set>;

IEnumerable<IGrouping<int, int>> lazyQuery = input
  .SelectMany(entry => entry.Value.Select(value => Tuple.Create(value, entry.Key)))
  .GroupBy(tuple => tuple.Item1, tuple => tuple.Item2);

foreach (IGrouping<int, int> group in lazyQuery)
{
  var key = group.Key;
  foreach (int value in group)
  {        
    // A Collection of e.g. 3,000,000 items is enumerated here for the first time, 
    // realizing each individual (per item) query result using the generator `yield return`.
    // This means calling break after the second iteration will only execute the LINQ for two items instead of 3,000,000.
  }
}

If you prefer to use the grouped collection as lookup table then use Enumerable.ToLookup:

Dictionary<int, List<int>> input = <Some init data set>;

// Query executes immediately, realizing all items
ILookup<int, int> lookupTable = input
  .SelectMany(entry => entry.Value.Select(value => Tuple.Create(value, entry.Key)))
  .ToLookup(tuple => tuple.Item1, tuple => tuple.Item2);

IEnumerable<int> valuesOfGroup = lookupTable[10];

foreach (int value in valuesOfGroup)
{        
}

LINQ generally uses deferred execution also called lazy evaluation. myItems.Select(item => item.X) will not immediately execute i.e. materialize. Only when explicitly enumerated by an Enumerator or when a realizer extension method is invoked. This lazy evaluation is implemented using the generator yield return. This generator allows big collection being enumerated in real-time by each query being applied item by item during each iteration.

Some realizer methods that immediately materialize the collection (execute the comoplete query). ToList(), ToDictionary(), Count()orToLookup()are some of them. Realizers are generallyEnumeratorconstructs likeforeach. Applying such a realizer on an IEnumerable` forces it to be evaluated by the compiler.

You did that twice in your query: first by calling ToList() and then by calling ToDictionary. This results in two complete iterations. One over the complete outer collection of IGrouping<int, int> items and the second to realize each individual group's items: ToDictionary(x=>x.Key, x=>x.ToList());

The improvement in the first solution is that the whole query (and sub queries) is deferred -> lazy evaluation. When iterating over the deferred query, the query is executed item by item, allowing to break after N realized items without wasting resources to materialize the complete collection.

The second solution query returns a ILookup<int, int>where ILookup implements IEnumerable. Compared to the original approach it eliminates the GroupBy, ToList and ToDictionary calls. Considering that ToLookup kind of wraps the combination of GroupBy and ToDictionary you still eliminated the extra iterations resulted by the call to ToList.

I appears that the data is generated, so that you can't control the data structure of the generated data. An improved data structure could improve/simplify data handling significantly, of course.
Your described scenario would perfectly benefit from having the data generator generating relational database tables instead of a simple (one way) lookup table. But it seems you are stuck to generate the reverse table yourself.

9
  • This seems to knock ~1/3 off the original cost for n=1M. You can strip another ~1/5 or so by using ValueTuple instead of Tuple, but it's still ~2times slower than a serial loop. (Disclaimer: didn't run many repeats, and this is on my particular machine with my particular random data set). – VisualMelon Aug 7 '20 at 18:01
  • ... though, this does get faster if you add an AsParallel (not as fast as serial in my silly little test though) – VisualMelon Aug 7 '20 at 18:04
  • Regarding that last bit, my tests suggest the opposite: that it will actually be faster to build the reverse dictionary from the forward dictionary rather than building both at the same time, but I've not properly tested this, and it is an interesting question. – VisualMelon Aug 7 '20 at 19:01
  • Yes was thinking about replacing the Tuple with a Value.Tuple too, but from what I found the Tuple is supposed to be slightly faster except when used as key. I really doubt that the iteration using for is 2 times faster. Indeed Enumerator has some overhead opposed to pure index based iteration, but the costs shouldn't have a factor of 2 and are generally neglectable.Also the workload is too small for parallel partitioning. The overhead introduced by threading and synchronization is too expensive. – BionicCode Aug 7 '20 at 19:59
  • Sequential data is generally difficult to parallelize and requires merging which also impacts the efficiency. I mean it all depend on n. If n is big enough you can parallelize. When you can determine the pivot n, you can offer a dynamic hybrid solution. But for small n (and n=1M is still small in this context or workload) this shouldn't pay off. The problem is the nested collections. I think there is not much you can do. The real improvement would be to find a better data structure, that allows two way lookup like a bi-directional tree (undirected graph). – BionicCode Aug 7 '20 at 19:59
-1

Divide and Conquor

Split the first set up into batches.

{
    1: [5,4] //<batch 1

    2: [4]   //<batch 2
    3: [10]  //<batch 2
}

Use an appropriate parallelisation technique (tasks, thread pool, etc...).

Each of the batches have the same sub problem. Apply a standard double for loop and construct the index.

// batch 1
{
    4: [1]
    5: [1] 
}

// batch 2
{
    4: [2]   
    10: [3]
}

Now catenate the dictionaries. Best done two at a time. If the key only exist in one dictionary then preserve the entry into the new dictionary. If it is in both merge their lists, and add to the new dictionary.

You can optimise this by not even bothering with having a new dictionary. The left hand dictionary simple has new keys inserted into it, or its key's values are appended to.

{
    4: [1, 2] //< append to list
    5: [1]    //< preexisting
    10: [3]   //< new key
}

This algorithm is still O(N), but if it can be perfectly executed in parallel can achieve a runtime of roughly O(logN). However caveats.

This presumes a dictionary data structures that has O(1) insert and O(N) merge qualities, as well as a List with O(1) catenation. If not blow out the runtime to O(N) or O(N^2).

The constant, and scaled overhead in parallelisation are large so this won't help much on small data sets, and is probably counter productive.

4
  • The data set is large (flattened it comes about 3 million records in a typical case.) I will try this Thanks for the answer :) – Jeremy Jul 30 '20 at 17:01
  • 2
    As you wrote, the dictionary merge is O(N) (and the splitting as well, which you forgot to mention), and since you cannot ignore this in the algorithm, the O(log N) statement is misleading. – Doc Brown Jul 31 '20 at 5:17
  • Good point @DocBrown. My mind was analysing the parallel execution time. I hope my edit clarifies this. – Kain0_0 Aug 1 '20 at 12:04
  • 1
    @Kain0_0: an algorithm which is O(N) is still O(N) when executed in parallel by a fixed number of processing units, not O(log N). And I still fail to see where a dictionary merge will benefit from parallelization. – Doc Brown Aug 1 '20 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.