Can a simple multi-dimensional array dereference be slow?
I'm struggling to understand the output I'm getting from gprof.
I have a simple wrapper class around a 2D array that I need to be contiguous in memory.
Its constructor and the method I use to access values are:
Array2d::Array2d(int size, double initialValue)
: mSize(size) {
data = new double *[size];
data[0] = new double[size * size];
for (int i = 1; i < size; ++i) {
data[i] = data[0] + i * size;
}
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
data[i][j] = initialValue;
}
}
}
double &Array2d::operator()(int i, int j) {
return data[i][j];
}
In the numerical code I'm working on, this is one output I obtained from gprof:
% cumulative self self total
time seconds seconds calls ms/call ms/call name
49.33 34.80 34.80 43507867293 0.00 0.00 Array2d::operator()(int, int)
18.05 47.53 12.73 jacobi(Array2d&, Array2d&, int, int, double, double, double, int)
I'm surprised to see that almost 50% of the running time is spent accessing values from the array.
This Array2d class replaced the use of std::vector<double>, which was much faster.
What I am failing to understand here?
c++ pointers gprof
asked Nov 13 '18 at 21:47
jehutyjehuty
301418
add a comment |
I'm struggling to understand the output I'm getting from gprof.
I have a simple wrapper class around a 2D array that I need to be contiguous in memory.
Its constructor and the method I use to access values are:
Array2d::Array2d(int size, double initialValue)
: mSize(size) {
data = new double *[size];
data[0] = new double[size * size];
for (int i = 1; i < size; ++i) {
data[i] = data[0] + i * size;
}
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
data[i][j] = initialValue;
}
}
}
double &Array2d::operator()(int i, int j) {
return data[i][j];
}
In the numerical code I'm working on, this is one output I obtained from gprof:
% cumulative self self total
time seconds seconds calls ms/call ms/call name
49.33 34.80 34.80 43507867293 0.00 0.00 Array2d::operator()(int, int)
18.05 47.53 12.73 jacobi(Array2d&, Array2d&, int, int, double, double, double, int)
I'm surprised to see that almost 50% of the running time is spent accessing values from the array.
This Array2d class replaced the use of std::vector<double>, which was much faster.
What I am failing to understand here?
c++ pointers gprof
asked Nov 13 '18 at 21:47
jehutyjehuty
301418
Why are you using more than one pointer ?
– Sid S
Nov 13 '18 at 21:50
2
Are you sure the problem is in that part of the code? It's not because your function is called 43 billion times? (In little under 35 seconds in total)
– Some programmer dude
Nov 13 '18 at 21:51
1
@Yksisarvinen: The array initialization is super wierd, but I think it may actually be valid. There is a block of memory for all of the elements contiguously, and each element indatapoints to a "row",sizeapart. Bizarre, but it should work.
– Mooing Duck
Nov 13 '18 at 21:54
1
That's not a multi-dimensional array (an array of arrays). Its an array of pointers to arrays; they're not synonymous. the former can be very cache friendly; the latter not-so-much. But at least the backdrop is contiguous, so there's hope.
– WhozCraig
Nov 13 '18 at 21:56
@MooingDuck Yep, hadn't seen that kind of thing for a while.
– juanchopanza
Nov 13 '18 at 21:56
add a comment |
I'm struggling to understand the output I'm getting from gprof.
I have a simple wrapper class around a 2D array that I need to be contiguous in memory.
Its constructor and the method I use to access values are:
Array2d::Array2d(int size, double initialValue)
: mSize(size) {
data = new double *[size];
data[0] = new double[size * size];
for (int i = 1; i < size; ++i) {
data[i] = data[0] + i * size;
}
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
data[i][j] = initialValue;
}
}
}
double &Array2d::operator()(int i, int j) {
return data[i][j];
}
In the numerical code I'm working on, this is one output I obtained from gprof:
% cumulative self self total
time seconds seconds calls ms/call ms/call name
49.33 34.80 34.80 43507867293 0.00 0.00 Array2d::operator()(int, int)
18.05 47.53 12.73 jacobi(Array2d&, Array2d&, int, int, double, double, double, int)
I'm surprised to see that almost 50% of the running time is spent accessing values from the array.
This Array2d class replaced the use of std::vector<double>, which was much faster.
What I am failing to understand here?
c++ pointers gprof
asked Nov 13 '18 at 21:47
jehutyjehuty
301418
I'm struggling to understand the output I'm getting from gprof.
I have a simple wrapper class around a 2D array that I need to be contiguous in memory.
Its constructor and the method I use to access values are:
Array2d::Array2d(int size, double initialValue)
: mSize(size) {
data = new double *[size];
data[0] = new double[size * size];
for (int i = 1; i < size; ++i) {
data[i] = data[0] + i * size;
}
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
data[i][j] = initialValue;
}
}
}
double &Array2d::operator()(int i, int j) {
return data[i][j];
}
In the numerical code I'm working on, this is one output I obtained from gprof:
% cumulative self self total
time seconds seconds calls ms/call ms/call name
49.33 34.80 34.80 43507867293 0.00 0.00 Array2d::operator()(int, int)
18.05 47.53 12.73 jacobi(Array2d&, Array2d&, int, int, double, double, double, int)
I'm surprised to see that almost 50% of the running time is spent accessing values from the array.
This Array2d class replaced the use of std::vector<double>, which was much faster.
What I am failing to understand here?
c++ pointers gprof
c++ pointers gprof
asked Nov 13 '18 at 21:47
jehutyjehuty
301418
asked Nov 13 '18 at 21:47
jehutyjehuty
301418
asked Nov 13 '18 at 21:47
jehutyjehuty
301418
asked Nov 13 '18 at 21:47
jehutyjehuty
301418
asked Nov 13 '18 at 21:47
jehutyjehuty
301418
301418
Why are you using more than one pointer ?
– Sid S
Nov 13 '18 at 21:50
2
Are you sure the problem is in that part of the code? It's not because your function is called 43 billion times? (In little under 35 seconds in total)
– Some programmer dude
Nov 13 '18 at 21:51
1
@Yksisarvinen: The array initialization is super wierd, but I think it may actually be valid. There is a block of memory for all of the elements contiguously, and each element indatapoints to a "row",sizeapart. Bizarre, but it should work.
– Mooing Duck
Nov 13 '18 at 21:54
1
That's not a multi-dimensional array (an array of arrays). Its an array of pointers to arrays; they're not synonymous. the former can be very cache friendly; the latter not-so-much. But at least the backdrop is contiguous, so there's hope.
– WhozCraig
Nov 13 '18 at 21:56
@MooingDuck Yep, hadn't seen that kind of thing for a while.
– juanchopanza
Nov 13 '18 at 21:56
add a comment |
Why are you using more than one pointer ?
– Sid S
Nov 13 '18 at 21:50
2
Are you sure the problem is in that part of the code? It's not because your function is called 43 billion times? (In little under 35 seconds in total)
– Some programmer dude
Nov 13 '18 at 21:51
1
@Yksisarvinen: The array initialization is super wierd, but I think it may actually be valid. There is a block of memory for all of the elements contiguously, and each element indatapoints to a "row",sizeapart. Bizarre, but it should work.
– Mooing Duck
Nov 13 '18 at 21:54
1
That's not a multi-dimensional array (an array of arrays). Its an array of pointers to arrays; they're not synonymous. the former can be very cache friendly; the latter not-so-much. But at least the backdrop is contiguous, so there's hope.
– WhozCraig
Nov 13 '18 at 21:56
@MooingDuck Yep, hadn't seen that kind of thing for a while.
– juanchopanza
Nov 13 '18 at 21:56
Why are you using more than one pointer ?
– Sid S
Nov 13 '18 at 21:50
Why are you using more than one pointer ?
– Sid S
Nov 13 '18 at 21:50
2
2
Are you sure the problem is in that part of the code? It's not because your function is called 43 billion times? (In little under 35 seconds in total)
– Some programmer dude
Nov 13 '18 at 21:51
Are you sure the problem is in that part of the code? It's not because your function is called 43 billion times? (In little under 35 seconds in total)
– Some programmer dude
Nov 13 '18 at 21:51
1
1
@Yksisarvinen: The array initialization is super wierd, but I think it may actually be valid. There is a block of memory for all of the elements contiguously, and each element in
data points to a "row", size apart. Bizarre, but it should work.– Mooing Duck
Nov 13 '18 at 21:54
@Yksisarvinen: The array initialization is super wierd, but I think it may actually be valid. There is a block of memory for all of the elements contiguously, and each element in
data points to a "row", size apart. Bizarre, but it should work.– Mooing Duck
Nov 13 '18 at 21:54
1
1
That's not a multi-dimensional array (an array of arrays). Its an array of pointers to arrays; they're not synonymous. the former can be very cache friendly; the latter not-so-much. But at least the backdrop is contiguous, so there's hope.
– WhozCraig
Nov 13 '18 at 21:56
That's not a multi-dimensional array (an array of arrays). Its an array of pointers to arrays; they're not synonymous. the former can be very cache friendly; the latter not-so-much. But at least the backdrop is contiguous, so there's hope.
– WhozCraig
Nov 13 '18 at 21:56
@MooingDuck Yep, hadn't seen that kind of thing for a while.
– juanchopanza
Nov 13 '18 at 21:56
@MooingDuck Yep, hadn't seen that kind of thing for a while.
– juanchopanza
Nov 13 '18 at 21:56
add a comment |
1 Answer
1
active
oldest
votes
I'm surprised to see that almost 50% of the running time is spent
accessing values from the array.
We cannot say much about this without seeing your code. It is easily possible to write code that has higher percentage of a single call. Consider
int main() {
while(true){
foo();
}
}
A profiler will tell you that close to 100% of the runtime is spend in foo. Does that mean foo is slow? No, we dont know.
The percentages you get from the profiler rather give you a hint to where the hot spots are in your code. If you know that 50% of the time is spend in one particular function call, then you know that this is a good canditate for improving performance. If you optimize this one function call you can achieve a speedup of up to x2 (cf amdahls law).
On the other hand, a function that uses only 0.1% of the total runtime can be made 1000-times faster without a significant impact on the total runtime.
Whether your element access is slow or fast, you can only know if you implement a second variant, leave everything else in the code as is and repeat the profiling. The variant that leads to a higher percentage performs worse.
answered Nov 13 '18 at 22:05
user463035818user463035818
17.1k42766
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53290002%2fcan-a-simple-multi-dimensional-array-dereference-be-slow%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I'm surprised to see that almost 50% of the running time is spent
accessing values from the array.
We cannot say much about this without seeing your code. It is easily possible to write code that has higher percentage of a single call. Consider
int main() {
while(true){
foo();
}
}
A profiler will tell you that close to 100% of the runtime is spend in foo. Does that mean foo is slow? No, we dont know.
The percentages you get from the profiler rather give you a hint to where the hot spots are in your code. If you know that 50% of the time is spend in one particular function call, then you know that this is a good canditate for improving performance. If you optimize this one function call you can achieve a speedup of up to x2 (cf amdahls law).
On the other hand, a function that uses only 0.1% of the total runtime can be made 1000-times faster without a significant impact on the total runtime.
Whether your element access is slow or fast, you can only know if you implement a second variant, leave everything else in the code as is and repeat the profiling. The variant that leads to a higher percentage performs worse.
answered Nov 13 '18 at 22:05
user463035818user463035818
17.1k42766
add a comment |
I'm surprised to see that almost 50% of the running time is spent
accessing values from the array.
We cannot say much about this without seeing your code. It is easily possible to write code that has higher percentage of a single call. Consider
int main() {
while(true){
foo();
}
}
A profiler will tell you that close to 100% of the runtime is spend in foo. Does that mean foo is slow? No, we dont know.
The percentages you get from the profiler rather give you a hint to where the hot spots are in your code. If you know that 50% of the time is spend in one particular function call, then you know that this is a good canditate for improving performance. If you optimize this one function call you can achieve a speedup of up to x2 (cf amdahls law).
On the other hand, a function that uses only 0.1% of the total runtime can be made 1000-times faster without a significant impact on the total runtime.
Whether your element access is slow or fast, you can only know if you implement a second variant, leave everything else in the code as is and repeat the profiling. The variant that leads to a higher percentage performs worse.
answered Nov 13 '18 at 22:05
user463035818user463035818
17.1k42766
add a comment |
I'm surprised to see that almost 50% of the running time is spent
accessing values from the array.
We cannot say much about this without seeing your code. It is easily possible to write code that has higher percentage of a single call. Consider
int main() {
while(true){
foo();
}
}
A profiler will tell you that close to 100% of the runtime is spend in foo. Does that mean foo is slow? No, we dont know.
The percentages you get from the profiler rather give you a hint to where the hot spots are in your code. If you know that 50% of the time is spend in one particular function call, then you know that this is a good canditate for improving performance. If you optimize this one function call you can achieve a speedup of up to x2 (cf amdahls law).
On the other hand, a function that uses only 0.1% of the total runtime can be made 1000-times faster without a significant impact on the total runtime.
Whether your element access is slow or fast, you can only know if you implement a second variant, leave everything else in the code as is and repeat the profiling. The variant that leads to a higher percentage performs worse.
answered Nov 13 '18 at 22:05
user463035818user463035818
17.1k42766
I'm surprised to see that almost 50% of the running time is spent
accessing values from the array.
We cannot say much about this without seeing your code. It is easily possible to write code that has higher percentage of a single call. Consider
int main() {
while(true){
foo();
}
}
A profiler will tell you that close to 100% of the runtime is spend in foo. Does that mean foo is slow? No, we dont know.
The percentages you get from the profiler rather give you a hint to where the hot spots are in your code. If you know that 50% of the time is spend in one particular function call, then you know that this is a good canditate for improving performance. If you optimize this one function call you can achieve a speedup of up to x2 (cf amdahls law).
On the other hand, a function that uses only 0.1% of the total runtime can be made 1000-times faster without a significant impact on the total runtime.
Whether your element access is slow or fast, you can only know if you implement a second variant, leave everything else in the code as is and repeat the profiling. The variant that leads to a higher percentage performs worse.
answered Nov 13 '18 at 22:05
user463035818user463035818
17.1k42766
answered Nov 13 '18 at 22:05
user463035818user463035818
17.1k42766
answered Nov 13 '18 at 22:05
user463035818user463035818
17.1k42766
answered Nov 13 '18 at 22:05
user463035818user463035818
17.1k42766
17.1k42766
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53290002%2fcan-a-simple-multi-dimensional-array-dereference-be-slow%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Why are you using more than one pointer ?
– Sid S
Nov 13 '18 at 21:50
2
Are you sure the problem is in that part of the code? It's not because your function is called 43 billion times? (In little under 35 seconds in total)
– Some programmer dude
Nov 13 '18 at 21:51
1
@Yksisarvinen: The array initialization is super wierd, but I think it may actually be valid. There is a block of memory for all of the elements contiguously, and each element in
datapoints to a "row",sizeapart. Bizarre, but it should work.– Mooing Duck
Nov 13 '18 at 21:54
1
That's not a multi-dimensional array (an array of arrays). Its an array of pointers to arrays; they're not synonymous. the former can be very cache friendly; the latter not-so-much. But at least the backdrop is contiguous, so there's hope.
– WhozCraig
Nov 13 '18 at 21:56
@MooingDuck Yep, hadn't seen that kind of thing for a while.
– juanchopanza
Nov 13 '18 at 21:56