Questions tagged [localityofreference]
21 questions
17
votes
1 answer
Arrays vs Linked Lists in terms of locality
Say we have an unsorted array and linked list.
The worst case when searching for an element for both data structures would be O( n ), but my question is:
Would the array still be way faster because of the use of spatial locality within the cache, or…
Kacy
- 3,330
- 4
- 29
- 57
12
votes
4 answers
Why is it worse to initialize a two dimensional array like this?
for(int i = 0; i<100; i++)
for(int j = 0; j<100; j++)
array[j][i] = 0;
// array[i][j] = 0;
My professor said it was much more costly to initialize a two dimensional array in the first way as opposed to the second. Can…
ordinary
- 5,943
- 14
- 43
- 60
10
votes
2 answers
Does partition function gives quick sort its locality of reference?
Does partition function gives quick sort its locality of reference ?
If it does, how ?
I mean what is there in quicksort which gives it locality of reference when compared to other algorithms such as merge sort or heap sort ?
I also read that
"The…
rachitnaruzu
- 128
- 1
- 8
4
votes
2 answers
Locality of Reference - English explanation for equidistant locality
I am reading the Wikipedia article on Locality of Reference, and I cannot help but find the explanation given for Equidistant Locality to be rather cryptic.
I cannot really make much sense of it, and I wondered if anyone could make an attempt to…
Tony The Lion
- 61,704
- 67
- 242
- 415
4
votes
2 answers
C++ Jumbling classes to enhance locality of reference?
Should we organize classes based on locality rather than conceptually?
Hypothetically, suppose we write a program to simulate a real-world environment which has three objects: a car, road and tree. Conventional OOP design suggests to conceptually…
Agrim Pathak
- 3,047
- 4
- 27
- 43
4
votes
1 answer
Spacial Locality in loops
From what I understand, spacial locality has to do with nearby memory being used in the nearby future. However I was wondering if a loop is executed many times, does this lead to good spacial locality? Thanks in advance, and sorry if I'm hard to…
user3277606
- 89
- 7
4
votes
4 answers
Reducing Instruction Cache misses (in C++)
Let's say I have a C++ class whose implementation looks something like this:
// ...
MyClass::iterativeFunction() {
for (int i = 0; i < 1000000; i++) {
performAction(i);
}
}
MyClass::performAction(int index) {
// Block of…
Ephemera
- 8,672
- 8
- 44
- 84
4
votes
1 answer
Cache use, spatial locality, and latency
I am learning cache operations with regard to spatial locality. (My references so far are Principles of Parallel Programming by Lin and Snyder, this tutorial, and of course Wikipedia.)
Take the following example, compiled with gcc, running on…
Christopher O'Brien
- 118
- 6
2
votes
2 answers
virtual member functions are good or bad for locality in modern CPUs?
Considering the new CPUs with new instructions for moving and new memory controllers, if in C++ I have a vector of Derived objects where Derived is composed of virtual member functions, is this a good or a bad thing for the locality ?
And what if I…
user2485710
- 9,451
- 13
- 58
- 102
2
votes
1 answer
Do C# collections care about cache friendlyness?
I've been running a lot of tests comparing an array of structs with an array of classes and a list of classes. Here's the test I've been running:
struct AStruct {
public int val;
}
class AClass {
public int val;
}
static void…
Alejandro Guillen
- 41
- 1
- 4
1
vote
1 answer
Why solving the two sum problem using a 2 nested loops, O(n^2) complexity, run much faster when only changing the loops counter logic?
Solving the two sum problem can be implemented using an O(n) complexity algorithm but, I just tried out the O(n^2) complexity which is the naive approach using 2 nested loops that check the sum of each ith integer with each of the rest integers…
Shaaer
- 527
- 5
- 17
1
vote
0 answers
HBase row key design: hotspotting vs. locality of reference
Consider a hypothetical HBase table.
The key must encode a 3-tuple (k, m, n) of integers between 0 and 1000.
The typical read is a range query over m and n, fixing a value of k.
The read load is exponentially distributed with respect to k. In…
Carl Patenaude Poulin
- 6,238
- 5
- 24
- 46
1
vote
1 answer
Principle of Locality and Call Instructions
In discussing the principle of locality, my textbook makes the following statements:
Except for branch and call instructions, which constitute only a small
fraction of all program instructions, program execution is sequential.
Hence, in most…
handler's handle
- 375
- 1
- 2
- 10
1
vote
0 answers
Accessing another object field variables performance cost (locality of reference)
Reading this question and this answer I know that accessing fields will cost some performance in AOT compilers (thanks to JVM I can forget about it)
Now please guide me about this scenario:
public class Foo
{
Object fooObject;
}
public…
Alireza Mohamadi
- 751
- 1
- 6
- 22
1
vote
2 answers
function pointer returning another function pointer in C++ with locality
Considering the fact that a pointer to a function returning another pointer to another function is the mechanism used in C to introduce some runtime polymorphism/callbacks, What is the equivalent way to implement this in C++ while improving locality…
user2485710
- 9,451
- 13
- 58
- 102