Mini-git class performance issue

Question

I want to build Git class where i can store integers. FilesSet is where I store current state of integers. Commits' key is basically commit number so I can checkout pretty fast. Hashes is used for quick search of hashes that I need in commit part.

Update is for updating current state of integers.

In Commit I want to save a copy of current state and do it fast. First of all I don't want to compare arrays of integers, so I calculate hash of current state. Then if Hashes already has that hash as a key, I add to Commits Pair of commitNumber and integer array that corresponds to that hash so I won't have to store another copy of array. And in Hashes of this key I add commit Number so I can see which commits have that hash. This one is a bottleneck for my solution.

In Checkout I basically get int that I need by arguments. I think this method is already really fast. I need this class to be fast but I can't really provide test cases as they are hidden at my college testing system. My current solution is too slow with int Commit() . Here it is :

using System.Collections.Generic;
using System.Linq;
using System;

namespace GitTask
{
    public class Git
    {
        int[] FilesSet { get; set; }
        Dictionary<int, int[]> Commits { get; set; }
        SortedList<int, List<int>> Hashes { get; set; }

        public Git(int filesCount)
        {
            FilesSet = new int[filesCount];
            Commits = new Dictionary<int, int[]>();
            Hashes = new SortedList<int, List<int>>();
        }

        public void Update(int fileNumber, int value)
        {
            FilesSet[fileNumber] = value;
        }

        public int Commit()
        {
            var commitNumber = Commits.Count;
            var tempHash = GetMyHashCode(FilesSet);

            if (Hashes.TryGetValue(tempHash, out List<int> key))
            {
                Commits.Add(commitNumber, Commits[key[0]]);
                Hashes[tempHash].Add(commitNumber);
                return commitNumber;
            }
            Commits.Add(Commits.Count, FilesSet.Clone() as int[]);
            Hashes.Add(tempHash, new List<int>(new int[] { commitNumber }));
            return commitNumber;
        }

        public int Checkout(int commitNumber, int fileNumber)
        {
            if (commitNumber >= Commits.Count)
                throw new ArgumentException();
            else
            {
                var commit = Commits[commitNumber];
                return commit[fileNumber];
            }
        }

        private int GetMyHashCode(int[] array)
        {
            int result = 0;
            for (int i = 0; i < array.Length; ++i)
            {
                result = unchecked(result * 31 + array[i]);
            }
            return result;
        }
    }
}

I expect you to come up with tips on speeding it up or creating new kind of storing files. I also tried to measure performance of methods and it seems like calculating hash of big array is a problem and adding to SortedList<int,List<int>> is a problem as well.

What I would recommend is to try to space it more (use paragraphs) :) — IEatBagels
– IEatBagels, Commented Sep 17, 2019 at 19:33
How much of the API is imposed by the spec and how much is amenable to suggestions for redesign? — Peter Taylor
– Peter Taylor, Commented Sep 18, 2019 at 7:09
The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. — Toby Speight
– Toby Speight, Commented Sep 18, 2019 at 8:26
Other than the performance is too slow are there any other issues? Does the code work as expected? — pacmaninbw
– pacmaninbw ♦, Commented Sep 18, 2019 at 14:20
@pacmaninbw there's no other problems rather than speed. Code works correct to me. — Jubick
– Jubick, Commented Sep 18, 2019 at 14:25

Pieter Witvoet · Accepted Answer · 2019-09-18 13:16:28Z

Hash code collisions

There's a problem with Commit: matching hash codes do not mean that two objects are equal ('pigeonhole principle'). For example, both [1, 0] and [0, 31] have hash code 31. You can only be sure that objects are not equal when their hash codes don't match - the inverse is not true.

Also, are you sure that reusing arrays is worth the effort? If filesCount is small, then the savings are small as well, and if filesCount is large, then the likelyhood that a specific state has occurred before is probably very small.

Multiple smaller arrays

One alternative is to divide the state into multiple smaller arrays. This limits the impact of individual changes: you only need to copy a 'sub-array' (and create a new 'array-of-arrays'), instead of copying the full state. This also increases the likelyhood that a particular sub-array has occurred before, although I do not think that is something you need to be concerned about.

In Git terms, this is similar to using multiple files instead of a single large file. Committing changes to a single file only creates a new blob for the modified file and a new tree object that references the new blob (and older blobs for unmodified files).

Change-sets

Another alternative is to store a change-set for each value, using a binary search to find the value for a particular commit number. This can save a lot of space, but it'll make checkouts slower. Whether that trade-off is worth it depends on the intended use of this class.

Other notes

Instead of Clone() as int[], you can use Linq's ToArray() method.
I'd put the last 4 lines of Commit inside an else statement, to make it clearer that these are two mutually exclusive paths.
On the other hand, I would not use an else statement in Checkout - the if check is an 'early-out' guard clause, not a full-blown separate path.
In Checkout, an ArgumentOutOfRangeException might be better suited. You may also want to guard against negative values. And why not check for invalid file numbers as well?

Peter Taylor · Accepted Answer · 2019-09-19 07:00:45Z

       if (Hashes.TryGetValue(tempHash, out List<int> key))
       {
           Commits.Add(commitNumber, Commits[key[0]]);
           Hashes[tempHash].Add(commitNumber);

Be consistent: you've already got an alias for Hashes[tempHash], so use it.

Also, on the subject of names, why tempHash instead of just hash? And key for the value of a KeyValuePair is a tad confusing.

I also tried to measure performance of methods and it seems like calculating hash of big array is a problem and adding to SortedList<int,List<int>> is a problem as well.

Well done for profiling. Both of those problems seem to me to have the same solution: don't do it.

The hash can be updated incrementally. FWIW, real solutions do this using a Merkle tree. To make this robust you need to do something about the FilesSet property. You should only expose the data in read-only form (e.g. as IReadOnlyList<int>), and if you have a setter it should take a defensive copy and recalculate the hash from scratch. But I'd be strongly tempted to remove the property and the Update method and replace them with an indexer.

As to the second: why use SortedList? What advantage does it give here over a Dictionary?

Aside from those points, I think the design is back to front. It would be simpler to do things the way version control systems actually do it: the commit version (tag) references the hash, and the hash references the data.

Stack Exchange Network

Mini-git class performance issue

2 Answers 2

Hash code collisions

Multiple smaller arrays

Change-sets

Other notes

You must log in to answer this question.

Hot Network Questions

Mini-git class performance issue

2 Answers 2

Hash code collisions

Multiple smaller arrays

Change-sets

Other notes

You must log in to answer this question.

Related

Hot Network Questions