Serving the Quantitative Finance Community

  • 1
  • 6
  • 7
  • 8
  • 9
  • 10
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz --- generic programming

February 8th, 2017, 9:03 am

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. 
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: C++ quiz --- generic programming

February 8th, 2017, 10:00 am

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.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz --- generic programming

February 8th, 2017, 10:43 am

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
(553 Bytes) Downloaded 112 times
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: C++ quiz --- generic programming

February 8th, 2017, 11:55 am

Thanks for the code! I'll look at it tonight, right now I have 8 hysterical kids running around!
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz --- generic programming

February 8th, 2017, 12:24 pm

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.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz --- generic programming

February 8th, 2017, 2:33 pm

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
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz --- generic programming

February 8th, 2017, 3:24 pm

BKmovector.cpp
(698 Bytes) Downloaded 109 times
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.
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: C++ quiz --- generic programming

February 8th, 2017, 4:27 pm

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?)
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: C++ quiz --- generic programming

February 8th, 2017, 4:31 pm

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];
}
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: C++ quiz --- generic programming

February 8th, 2017, 4:39 pm

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>

std::chrono::steady_clock::time_point start, end;
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
        // ---------------------------------------------
        start = std::chrono::steady_clock::now();

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

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

        // ---------------------------------------------
        // Initialise storage
        // ---------------------------------------------
        start = std::chrono::steady_clock::now();

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

        end = std::chrono::steady_clock::now();
        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 
            // ---------------------------------------------
            start = std::chrono::steady_clock::now();
            
            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];
            }
            
            end = std::chrono::steady_clock::now();
            algo_time += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
    
            // ---------------------------------------------
            // flip 
            // ---------------------------------------------
            start = std::chrono::steady_clock::now();
            
            std::swap(v0,v1);
            
            end = std::chrono::steady_clock::now();
            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;   
    }
}
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: C++ quiz --- generic programming

February 8th, 2017, 4:46 pm

std::array instead std::vector
alloc storage: 23103
init  storage: 9613
algo  time   : 6462562
flip  time   : 672761
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz --- generic programming

February 8th, 2017, 4:46 pm

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)
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: C++ quiz --- generic programming

February 8th, 2017, 4:48 pm

.. 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
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: C++ quiz --- generic programming

February 8th, 2017, 4:49 pm

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! 
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: C++ quiz --- generic programming

February 8th, 2017, 5:01 pm

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.