0

I have a problem that I don't understand, in that code:

ilProbekUcz= valuesUcz.Count; //valuesUcz is the list of <float[]>
for (int i = 0; i < ilWezlowDanych; i++) nodesValueArrayUcz[i] = new BitArray(ilProbekUcz);
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 0; i < ilProbekUcz; i++)
{
        int index = 0;
       linia = (float[])valuesUcz[i];//removing this line not solve problem
        for (int a = 0; a < ileRazem; a++)
                for (int b = 0; b < ileRazem; b++)
                        if (a != b)
                        {
                                bool value = linia[a] >= linia[b];
                                nodesValueArrayUcz[index][i] = value;
                                nodesValueArrayUcz[ilWezlowDanychP2 + index][i] = !value;
                                index++;
                        }
}
sw.Stop();

When i increase size of valuesUcz 2x, time of execution is 4x bigger

When i increase size of valuesUcz 4x, time of execution is 8x bigger etc ...

(ileRazem,ilWezlowDanych is the same)

I understand: increase of ilProbekUcz increases size of BitArrays but i test it many times and it is no problem - time should grow linearly - in code: 

ilProbekUcz= valuesUcz.Count; //valuesTest is the list of float[]
for (int i = 0; i < ilWezlowDanych; i++) nodesValueArrayUcz[i] = new BitArray(ilProbekUcz);
BitArray test1 = nodesValueArrayUcz[10];
BitArray test2 = nodesValueArrayUcz[20];
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 0; i < ilProbekUcz; i++)
{
        int index = 0;
       linia = (float[])valuesUcz[i];//removing this line not solve problem
        for (int a = 0; a < ileRazem; a++)
                for (int b = 0; b < ileRazem; b++)
                        if (a != b)
                        {
                                bool value = linia[a] >= linia[b];
                                test1[i] = value;
                                test2[i] = !value;
                                index++;
                        }
}

time grows linearly, so the problem is to take a BitArray from the array...

Is any method to do it faster ? (i want time to grow linearly)

Improve this question
7
  • 1
    ...time grows linearly, so the problem is to take a BitArray from the array... Is any metod to do it faster ? (i want time to grows lineary) ... O(1 * n) = O(2 * n) = ... = O(c * n) = O(n), where c is a constant. Commented Aug 30, 2018 at 10:35
  • What is ileRazem? Commented Aug 30, 2018 at 10:38
  • size of linia - i measure times at 1440, 2880, 5760 Commented Aug 30, 2018 at 10:40
  • but "linia" is not a problem, I turned it into a constant and times are the same Commented Aug 30, 2018 at 10:46
  • You can remove linia and use bool value = valuesUcz[ i ][ a ] >= valuesUcz[ i ][ b ];. You said it didn't help. If you don't tell as what you want to accomplish we can not help you. All we can see is 3 for loops doing something. Commented Aug 30, 2018 at 11:21

1 Answer 1

Reset to default
1

You have to understand that measuring time there are many factors that makes them inacurate. The biggest factor when you have huuuuuge arrays as in your example is cashe misses. Many times the same thing written when taking account of cashe, can be as much as 2-5 or more times faster. Two words how cashe works, very roughly. Cache is memory inside cpu. It is waaaaaaaaaaaaaay faster than ram so when you want to fetch a variable from memory you want to make sure this variable is stored in cache and not in ram. If it is stored in cache we say we have a hit otherwise a miss. Some times, not so often, a program is so big that it stores variables in hard drive. In that case you have a huuuuuuuuuuuge hit in delay when you fetch these! An example of cache:

Lets say we have an array of 10 elements in memory(ram)

enter image description here

when you get the first element testArray[0], because testArray[0] is not in cache the cpu brings this value along with a number(lets say 3, the number depends on the cpu) of adjacent elements of the array eg it stores to cache testArray[0], testArray[1], testArray[2], testArray[3]

enter image description here

Now when we get testArray[1] it is in cache so we have a hit. The same with testArray[2] and testArray[3]. testArray[4] isn't in cache so it gets testArray[4] along with another 3 testArray[5], testArray[6], testArray[7]

enter image description here

and so on...
Cache misses are very costly. That means you may expect an array of double the size is going to be accessible double the time. But this is not true. Bigger arrays more misses and the time may increase 2 or 3 or 4 or more times from what you expect. This is normal. In your example that is what is happening. From 100 million elemensts(first array) you go t0 400 million (second one). The missesare not double but waaay more as you saw. A very cool trick has to do with the way you access an array. In your example ba1[j][i] = (j % 2) == 0; is way worse than ba1[i][j] = (j % 2) == 0;. The same with ba2[j][i] = (j % 2) == 0; and ba1[i][j] = (j % 2) == 0;. You can test it. Just reverse i and j. It has to do with the way the 2D array is stored in memory so in the second case you have more hits that the first one.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thank You, i know that ba[i][j] is faster - it time grows lineary ;), the algorithm needs to fill them in order from first code ... i need to think abaut it - but i have a question: do you know some metods let me affects what is in cache ?
@barpas You can't. Cpu does it automatically as long as data is sequental, one next to other. In your loops 99,9999% of the time is wasted in fetching values to cache. So if these values are not next to each other you have big issue. You have to understand array[0][0] and array[1][0] are not together in memory. But array[0][0] and array[0][1] are! Tell me what your algorithm does so I can help you in your code.
as You can see there is array of lines, thre are values - it compare every values in linie (float[]) and put result to proper bitarray, lines are ordered by time, bitarray are ordered by compared values each bit in bitarray is next period of time
@barpas I need the exact code otherwise i cant help you

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.