SERVING THE QUANTITATIVE FINANCE COMMUNITY

• 1
• 6
• 7
• 8
• 9
• 10

Cuchulainn
Posts: 60835
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: C++ quiz --- generic programming

This time C and D are best? The ranking looks a bit unpredictable?
In this case, I took larger NX, so as far as compile time is concerned it becomes slower for larger NX (in VS the default stack size is 1 Mb and it extends memory in working units of 64K),
I suppose for larger NX, swapping will be less efficient than assignment v2 = v1.

Looking back, option C (std::move_backward()) is a good all-rounder.
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik

outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: C++ quiz --- generic programming

Swapping pointers should be faster.

Eg in C you will do

double* v_t = &memory_a[0];
double* v_t_plus_1 = &memory_b[0]

And then flip memory_a and memory_b around for even/odd loop step.

No memory is allocated, no elements are moved, nothing cleared, ...

So I expect you measure something else, and if so then you are drawing wrong conclusion. Right now it's "magic" "empirial" and it should be simple science and logic.

I think the size and the stack are important elements for using vectors instead of array for large memory blocks, but swapping pointers should be fastest.

Another view is this; move the central code to some function and call it like this:

do_single_time_step(v1,v2);
do_single_time_step(v2,v1);

Then it's obvious there is zero overhead managing memory and copying things, right? You've separated container memory management from algorithms that act on them.

Cuchulainn
Posts: 60835
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: C++ quiz --- generic programming

Good point. I have indeed 2 aspects (as I mentiioned it is a fd 101 prototype)

1. the algo
2. memory allocation

And I want to know how long 1+2 takes.So yes, I am measuring more than just memory allocation.

In a fd scheme we need bot 1 and 2.. See the baseline code.
BTW do you use raw pointers? That's C! (nothing wrong with that, just saying).

//
Swapping pointers should be faster.
What you can do is to remove the algo part 1 of the 1+2 and see that it is so, maybe. But it is maybe a micro optimisation. You would expect STL to do it for you instead of hand-crafting a solution.
Attachments
baseline.cpp
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik

outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: C++ quiz --- generic programming

Thanks for the code! I'll look at it tonight, right now I have 8 hysterical kids running around!

Cuchulainn
Posts: 60835
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: C++ quiz --- generic programming

Thanks for the code! I'll look at it tonight, right now I have 8 hysterical kids running around!
Last week you had 2 kids! Fast worker.

I now filtered out the algo part so as to just compare the creation part:
NX: 2000, NT: 10000000
A. standard array way (baseline case) 27.0103
B. move of a range 80.8108
C. move backwards 8.73009
D. copy v2 = v1 3.88004
E. clear and copy 3.98004
F. define + init arrays in loop 5.02005
G. swap option 0.0200002 (using std::swap())
H. compile-time array 16.4102
// The much-publicised C++11 move is not  so great for this problem.
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik

Cuchulainn
Posts: 60835
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: C++ quiz --- generic programming

Swapping pointers should be faster.

Eg in C you will do

double* v_t = &memory_a[0];
double* v_t_plus_1 = &memory_b[0]
Here's an even huge swap in STL. Looks like zero overhead.
NX: 1000, NT: 1000000000
A. standard array way (baseline case) 1363.06
B. move of a range 3711.44
C. move backwards 506.84
D. copy v2 = v1 221.241
E. clear and copy 206.805
F. define + init arrays in loop 259.435
G. swap option 3.62936
H. compile-time array 760.292
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik

Cuchulainn
Posts: 60835
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: C++ quiz --- generic programming

BKmovector.cpp
Option "I" using a move assignment. All rounds (algo + creation) it is the fastest but I get value == 0. What am I doing wrong?
It's a nice puzzle.

The follow-on question is how to effectively use move ctor here. If at all.
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik

outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: C++ quiz --- generic programming

The kids are gone! I have 10 minutes now!

I think the best "move" woud be to move the vector as a whole, not element by element? (not sure if it's doable?)

outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: C++ quiz --- generic programming

Is this second line (copying result back in vold, inside the loop) good??
{
result[j] = a*vold[j - 1] + b*vold[j] + c*vold[j + 1];
vold[j] = result[j];
}

outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: C++ quiz --- generic programming

This (long) bit of code splits things out.  This variant uses a std::vector, 1.000x1.000, and it uses a std::swap inside the loop
./fdm_timer
alloc storage: 27916
init  storage: 8154
algo  time   : 4765080
flip  time   : 69888
#include <cstdint>
#include <chrono>
#include <iostream>
#include <vector>

int_least64_t alloc_time, init_time, algo_time, flip_time;

int main(void) {

int Nx = 1000;
int Nt = 1000;
double a = 2.0 / 59.0;
double b = 4.0 / 60.0;
double c = 1.0 / 61.0;

{
// ---------------------------------------------
// Allocate
// ---------------------------------------------

std::vector<double> v0(Nx);
std::vector<double> v1(Nx);

alloc_time = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();

// ---------------------------------------------
// Initialise storage
// ---------------------------------------------

for (int i=0; i<Nx; ++i)
v1[i] = 3.14;

init_time = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();

// ---------------------------------------------
// main loop
// ---------------------------------------------
algo_time = 0;
flip_time = 0;

for (std::size_t ti = 0; ti < Nt; ++ti) {

// ---------------------------------------------
// algo
// ---------------------------------------------

v0[0] = v1[0];
v0[v0.size() - 1] = v1[v1.size() - 1];

for (std::size_t j = 1; j < v0.size() - 1; ++j) {
v0[j] = a*v1[j - 1] + b*v1[j] + c*v1[j + 1];
}

algo_time += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();

// ---------------------------------------------
// flip
// ---------------------------------------------

std::swap(v0,v1);

flip_time += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();

}

std::cout << "alloc storage: " << alloc_time << std::endl;
std::cout << "init  storage: " << init_time << std::endl;
std::cout << "algo  time   : " << algo_time << std::endl;
std::cout << "flip  time   : " << flip_time << std::endl;
}
}


outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: C++ quiz --- generic programming

alloc storage: 23103
init  storage: 9613
algo  time   : 6462562
flip  time   : 672761

Cuchulainn
Posts: 60835
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: C++ quiz --- generic programming

The kids are gone! I have 10 minutes now!

I think the best "move" woud be to move the vector as a whole, not element by element? (not sure if it's doable?)
See my previous .cpp file I posted (it's a move ctor or assignment)
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik

outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: C++ quiz --- generic programming

.. timing is highly unstable, we need to wrap a 1000x loop around it?
Thijss-MacBook-Air:build thijs$./fdm_timer alloc storage: 23103 init storage: 9613 algo time : 6462562 flip time : 672761 Thijss-MacBook-Air:build thijs$ ./fdm_timer
alloc storage: 41490
init  storage: 13092
algo  time   : 9314978
flip  time   : 931780
Thijss-MacBook-Air:build thijs$./fdm_timer alloc storage: 54013 init storage: 12163 algo time : 8370276 flip time : 985036 Thijss-MacBook-Air:build thijs$ ./fdm_timer
alloc storage: 19226
init  storage: 7210
algo  time   : 6568961
flip  time   : 702387

outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: C++ quiz --- generic programming

The kids are gone! I have 10 minutes now!

I think the best "move" woud be to move the vector as a whole, not element by element? (not sure if it's doable?)
See my previous .cpp file I posted (it's a move ctor or assignment)
Yes, .. that's what I would expect to be much faster!

Cuchulainn
Posts: 60835
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: C++ quiz --- generic programming

The kids are gone! I have 10 minutes now!

I think the best "move" woud be to move the vector as a whole, not element by element? (not sure if it's doable?)
See my previous .cpp file I posted (it's a move ctor or assignment)
Yes, .. that's what I would expect to be much faster!
move ctor is very good, but I have a bug. Maybe it's just a stupid mistake but  the real when and why use it is TBD.
swap is just very good.
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik