SERVING THE QUANTITATIVE FINANCE COMMUNITY

  • 1
  • 6
  • 7
  • 8
  • 9
  • 10
 
User avatar
Cuchulainn
Posts: 59665
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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: April 29th, 2016, 1:40 pm

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: 59665
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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 28 times
 
User avatar
outrun
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

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: 59665
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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: 59665
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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: 59665
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: C++ quiz --- generic programming

February 8th, 2017, 3:24 pm

BKmovector.cpp
(698 Bytes) Downloaded 30 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: April 29th, 2016, 1:40 pm

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: April 29th, 2016, 1:40 pm

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: April 29th, 2016, 1:40 pm

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: April 29th, 2016, 1:40 pm

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: 59665
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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: April 29th, 2016, 1:40 pm

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: April 29th, 2016, 1:40 pm

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: 59665
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On