** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** - Page 811 - Computer Technical Help

Speaking on n**2 vs log n algorithms, I know as a complete certainty that the original BASIC language interpreter that Microsoft wrote used an n**2 algorithm in implementing their garbage collection. I also know that they really wished they would have used a log n alogarithm. I'm pretty sure that one of the factors in deciding to use an n**2 algorithm was memory usage.

Yep, that's one of the things I learn while practicing coding problems. There's always a tradeoff between space and speed. You want speed??? Okay then you will need to use space.

Also has anyone had to do interview questions on hackerrank? I signed up for indeed's prime, which is basically a copy of hired.com. Did the test, but I found that I spent too much time trying to parse input from their program rather than solving the problem. Ended up only solving 1/4 of the problems

(((

Quote

10-13-2015 , 01:45 AM

#20252

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

baltimore, interesting. thanks for answering.

Quote

10-13-2015 , 04:07 AM

#20253

adios

Carpal \'Tunnel

Join Date: Sep 2002 Posts: 22,535

Quote:

Originally Posted by CyberShark93

after discovering changing all my doubles to floats gave me an insane performance boost, i was wondering if i should change all my loop counters to unsigned short or something?

Probably won't help. The number of bits in an unsigned short tends to be 16, processor arithmetic opertions probably operate on 32 bit quantities.

Quote

10-13-2015 , 04:51 AM

#20254

CyberShark93

veteran

Join Date: Dec 2013 Posts: 3,325

Quote:

Originally Posted by adios

Probably won't help. The number of bits in an unsigned short tends to be 16, processor arithmetic opertions probably operate on 32 bit quantities.

Yeah, found that out yesterday through trial and error =)

But in general I think having the correct variable types gave me a lot more performance boost than say manually unrolling loops etc

Also the -fast-math and -o3 compiler flags helped a lot too, don't know if there are any more

Quote

10-13-2015 , 05:51 AM

#20255

CyberShark93

veteran

Join Date: Dec 2013 Posts: 3,325

Code:

void propagate(const param_t params, speed_t* cells, speed_t* tmp_cells)
{
    int ii,jj;            /* generic counters */
    /* loop over _all_ cells */
    for (ii = 0; ii < params.ny; ii++)
    {
        for (jj = 0; jj < params.nx; jj++)
        {
            int x_e,x_w,y_n,y_s;  /* indices of neighbouring cells */
            /* determine indices of axis-direction neighbours
            ** respecting periodic boundary conditions (wrap around) */
            y_n = (ii + 1) % params.ny;
            x_e = (jj + 1) % params.nx;
            y_s = (ii == 0) ? (ii + params.ny - 1) : (ii - 1);
            x_w = (jj == 0) ? (jj + params.nx - 1) : (jj - 1);
            /* propagate densities to neighbouring cells, following
            ** appropriate directions of travel and writing into
            ** scratch space grid */
            tmp_cells[ii *params.nx + jj].speeds[0]  = cells[ii*params.nx + jj].speeds[0]; /* central cell, */
                                                     /* no movement   */
            tmp_cells[ii *params.nx + x_e].speeds[1] = cells[ii*params.nx + jj].speeds[1]; /* east */
            tmp_cells[y_n*params.nx + jj].speeds[2]  = cells[ii*params.nx + jj].speeds[2]; /* north */
            tmp_cells[ii *params.nx + x_w].speeds[3] = cells[ii*params.nx + jj].speeds[3]; /* west */
            tmp_cells[y_s*params.nx + jj].speeds[4]  = cells[ii*params.nx + jj].speeds[4]; /* south */
            tmp_cells[y_n*params.nx + x_e].speeds[5] = cells[ii*params.nx + jj].speeds[5]; /* north-east */
            tmp_cells[y_n*params.nx + x_w].speeds[6] = cells[ii*params.nx + jj].speeds[6]; /* north-west */
            tmp_cells[y_s*params.nx + x_w].speeds[7] = cells[ii*params.nx + jj].speeds[7]; /* south-west */
            tmp_cells[y_s*params.nx + x_e].speeds[8] = cells[ii*params.nx + jj].speeds[8]; /* south-east */
        }
    }
}

suppose if i want to optimize a loop like this, I suspect that i'm getting cache misses, but how do I know that for sure? is there a way to analyse these sort of things?

i don't really like the performance of this loop, and i don't know if there is anything that could be done.

Code:

typedef struct {
    int nx;            /* no. of cells in x-direction */
    int ny;            /* no. of cells in y-direction */
    int max_iters;      /* no. of iterations */
    int reynolds_dim;  /* dimension for Reynolds number */
    float density;       /* density per link */
    float accel;         /* density redistribution */
    float omega;         /* relaxation parameter */
} param_t;

/* struct to hold the 'speed' values */
typedef struct {
    float speeds[9];
} speed_t;

Last edited by CyberShark93; 10-13-2015 at 05:56 AM.

Quote

10-13-2015 , 07:30 AM

#20256

skario

enthusiast

Join Date: Jan 2007 Posts: 87

This should be much faster assuming x86.

Code:

void propagate(const param_t params, speed_t* cells, speed_t* tmp_cells)
{
    int ii, jj, x_e, x_w, y_n, y_s;
    
    for (ii = 0; ii < params.ny; ii++)
    {
        y_n = (ii + 1) % params.ny;
        y_s = (ii == 0) ? (ii + params.ny - 1) : (ii - 1);

        x_w = params.nx - 1;
        jj = 0;
        x_e = 1;
        tmp_cells[ii * params.nx + jj].speeds[0] = cells[ii * params.nx + jj].speeds[0];
        tmp_cells[ii * params.nx + jj].speeds[1] = cells[ii * params.nx + x_w].speeds[1];
        tmp_cells[ii * params.nx + jj].speeds[2] = cells[y_s * params.nx + jj].speeds[2];
        tmp_cells[ii * params.nx + jj].speeds[3] = cells[ii * params.nx + x_e].speeds[3];
        tmp_cells[ii * params.nx + jj].speeds[4] = cells[y_n * params.nx + jj].speeds[4];
        tmp_cells[ii * params.nx + jj].speeds[5] = cells[y_s * params.nx + x_w].speeds[5];
        tmp_cells[ii * params.nx + jj].speeds[6] = cells[y_s * params.nx + x_e].speeds[6];
        tmp_cells[ii * params.nx + jj].speeds[7] = cells[y_n * params.nx + x_e].speeds[7];
        tmp_cells[ii * params.nx + jj].speeds[8] = cells[y_n * params.nx + x_w].speeds[8];

        for (jj = 1; jj < params.nx - 1; jj++)
        {
            x_w = jj - 1;
            x_e = jj + 1;
            tmp_cells[ii * params.nx + jj].speeds[0] = cells[ii * params.nx + jj].speeds[0];
            tmp_cells[ii * params.nx + jj].speeds[1] = cells[ii * params.nx + x_w].speeds[1];
            tmp_cells[ii * params.nx + jj].speeds[2] = cells[y_s * params.nx + jj].speeds[2];
            tmp_cells[ii * params.nx + jj].speeds[3] = cells[ii * params.nx + x_e].speeds[3];
            tmp_cells[ii * params.nx + jj].speeds[4] = cells[y_n * params.nx + jj].speeds[4];
            tmp_cells[ii * params.nx + jj].speeds[5] = cells[y_s * params.nx + x_w].speeds[5];
            tmp_cells[ii * params.nx + jj].speeds[6] = cells[y_s * params.nx + x_e].speeds[6];
            tmp_cells[ii * params.nx + jj].speeds[7] = cells[y_n * params.nx + x_e].speeds[7];
            tmp_cells[ii * params.nx + jj].speeds[8] = cells[y_n * params.nx + x_w].speeds[8];
        }

        x_w = params.nx - 2;
        jj = params.nx - 1;
        x_e = 0;
        tmp_cells[ii * params.nx + jj].speeds[0] = cells[ii * params.nx + jj].speeds[0];
        tmp_cells[ii * params.nx + jj].speeds[1] = cells[ii * params.nx + x_w].speeds[1];
        tmp_cells[ii * params.nx + jj].speeds[2] = cells[y_s * params.nx + jj].speeds[2];
        tmp_cells[ii * params.nx + jj].speeds[3] = cells[ii * params.nx + x_e].speeds[3];
        tmp_cells[ii * params.nx + jj].speeds[4] = cells[y_n * params.nx + jj].speeds[4];
        tmp_cells[ii * params.nx + jj].speeds[5] = cells[y_s * params.nx + x_w].speeds[5];
        tmp_cells[ii * params.nx + jj].speeds[6] = cells[y_s * params.nx + x_e].speeds[6];
        tmp_cells[ii * params.nx + jj].speeds[7] = cells[y_n * params.nx + x_e].speeds[7];
        tmp_cells[ii * params.nx + jj].speeds[8] = cells[y_n * params.nx + x_w].speeds[8];
    }
}

Quote

10-13-2015 , 08:04 AM

#20257

CyberShark93

veteran

Join Date: Dec 2013 Posts: 3,325

Quote:

Originally Posted by skario

This should be much faster assuming x86.

Code:

void propagate(const param_t params, speed_t* cells, speed_t* tmp_cells)
{
    int ii, jj, x_e, x_w, y_n, y_s;
    
    for (ii = 0; ii < params.ny; ii++)
    {
        y_n = (ii + 1) % params.ny;
        y_s = (ii == 0) ? (ii + params.ny - 1) : (ii - 1);

        x_w = params.nx - 1;
        jj = 0;
        x_e = 1;
        tmp_cells[ii * params.nx + jj].speeds[0] = cells[ii * params.nx + jj].speeds[0];
        tmp_cells[ii * params.nx + jj].speeds[1] = cells[ii * params.nx + x_w].speeds[1];
        tmp_cells[ii * params.nx + jj].speeds[2] = cells[y_s * params.nx + jj].speeds[2];
        tmp_cells[ii * params.nx + jj].speeds[3] = cells[ii * params.nx + x_e].speeds[3];
        tmp_cells[ii * params.nx + jj].speeds[4] = cells[y_n * params.nx + jj].speeds[4];
        tmp_cells[ii * params.nx + jj].speeds[5] = cells[y_s * params.nx + x_w].speeds[5];
        tmp_cells[ii * params.nx + jj].speeds[6] = cells[y_s * params.nx + x_e].speeds[6];
        tmp_cells[ii * params.nx + jj].speeds[7] = cells[y_n * params.nx + x_e].speeds[7];
        tmp_cells[ii * params.nx + jj].speeds[8] = cells[y_n * params.nx + x_w].speeds[8];

        for (jj = 1; jj < params.nx - 1; jj++)
        {
            x_w = jj - 1;
            x_e = jj + 1;
            tmp_cells[ii * params.nx + jj].speeds[0] = cells[ii * params.nx + jj].speeds[0];
            tmp_cells[ii * params.nx + jj].speeds[1] = cells[ii * params.nx + x_w].speeds[1];
            tmp_cells[ii * params.nx + jj].speeds[2] = cells[y_s * params.nx + jj].speeds[2];
            tmp_cells[ii * params.nx + jj].speeds[3] = cells[ii * params.nx + x_e].speeds[3];
            tmp_cells[ii * params.nx + jj].speeds[4] = cells[y_n * params.nx + jj].speeds[4];
            tmp_cells[ii * params.nx + jj].speeds[5] = cells[y_s * params.nx + x_w].speeds[5];
            tmp_cells[ii * params.nx + jj].speeds[6] = cells[y_s * params.nx + x_e].speeds[6];
            tmp_cells[ii * params.nx + jj].speeds[7] = cells[y_n * params.nx + x_e].speeds[7];
            tmp_cells[ii * params.nx + jj].speeds[8] = cells[y_n * params.nx + x_w].speeds[8];
        }

        x_w = params.nx - 2;
        jj = params.nx - 1;
        x_e = 0;
        tmp_cells[ii * params.nx + jj].speeds[0] = cells[ii * params.nx + jj].speeds[0];
        tmp_cells[ii * params.nx + jj].speeds[1] = cells[ii * params.nx + x_w].speeds[1];
        tmp_cells[ii * params.nx + jj].speeds[2] = cells[y_s * params.nx + jj].speeds[2];
        tmp_cells[ii * params.nx + jj].speeds[3] = cells[ii * params.nx + x_e].speeds[3];
        tmp_cells[ii * params.nx + jj].speeds[4] = cells[y_n * params.nx + jj].speeds[4];
        tmp_cells[ii * params.nx + jj].speeds[5] = cells[y_s * params.nx + x_w].speeds[5];
        tmp_cells[ii * params.nx + jj].speeds[6] = cells[y_s * params.nx + x_e].speeds[6];
        tmp_cells[ii * params.nx + jj].speeds[7] = cells[y_n * params.nx + x_e].speeds[7];
        tmp_cells[ii * params.nx + jj].speeds[8] = cells[y_n * params.nx + x_w].speeds[8];
    }
}

Hi!, thx for the help, this version is indeed faster, but do u mind giving me a quick explanation of why splitting up the inner loop like that helps performance?

Quote

10-13-2015 , 09:21 AM

#20258

skario

enthusiast

Join Date: Jan 2007 Posts: 87

Quote:

Originally Posted by CyberShark93

Hi!, thx for the help, this version is indeed faster, but do u mind giving me a quick explanation of why splitting up the inner loop like that helps performance?

It removes a slow modulo (%) operation from the inner loop. Also writing sequentially instead of reading sequentially is usually faster.

Quote

10-13-2015 , 05:57 PM

#20259

adios

Carpal \'Tunnel

Join Date: Sep 2002 Posts: 22,535

Quote:

Originally Posted by CyberShark93

Hi!, thx for the help, this version is indeed faster, but do u mind giving me a quick explanation of why splitting up the inner loop like that helps performance?

You might try compiling with C++ 11 and creating a move copy constructor for your speed_t struct. I have a lot of **** to do for a few days so I don't know when I'll get to it. The compiler probably optimizes this but it might be worth a try:

Just compute stuff like below once. Also you don't need to add jj when it is zero.
ii * params.nx

Quote

10-13-2015 , 07:39 PM

#20260

adios

Carpal \'Tunnel

Join Date: Sep 2002 Posts: 22,535

Quote:

Originally Posted by adios

Not the move copy constructor, overload the = operator with a move assignment.

Quote

10-13-2015 , 09:23 PM

#20261

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

Quote:

Originally Posted by Baltimore Jones

Happy to answer more questions. It is definitely possible that I'm bad at phone screens. I found it difficult to tell a compelling story about my career narrative, and until I started doing cool work with new technologies at the contract job I had nothing terribly interesting to discuss when they asked about my personal projects etc. (I had them, it was just very standard Rails and Backbone stuff). Still though, my phone screen rate was quite low as I said anyway. I can try to dig up the conversion rate of phone screen to next step.

I really struggled with this one as well. It is worse for me because I only have 2 jobs on my resume, and when they see someone my age, they are a little taken aback, I think. I tend to say that I prefer not to talk about whatever I was doing in my 20s, but it was nothing illegal.

My experience with recruiters was about the same as yours. There were a handful that were really out to help me. I took it upon myself to get some feedback about the interview from them. Not in a defensive way, just in a self-improving way, which is no huge deal if you have some rapport with them. I was getting feedback about being too advanced for whatever I was applying for, so I started applying for harder jobs.

As noted above, thanks for sharing. I read your post more than once.

Quote

10-13-2015 , 09:30 PM

#20262

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

Quote:

Originally Posted by iosys

smoke a joint before the phone screen

I'm pretty sure a willingness to get baked on medicine is a prereq for many jobs in SF.

If you are in a pinch, you can always grab one of those single shot bottles from the liquor store on the way to an interview. I don't condone drinking in public, and I do preach what I don't practice.

Quote

10-13-2015 , 10:36 PM

#20263

iosys

old hand

Join Date: Sep 2011 Posts: 1,753

I don't drink alcohol at all, I only drink well water or water that has been distilled to remove fluoride or whatever was in it.

I wouldn't mind if there was a ban on soda products, alcohol and other drinkable liquids that are bad for health.

I personally think that a lot of people drink too much energy drinks or coffee and that the perceived normal usage is probably way to much.
I'm not saying that coffee is bad,, it just is used to much and people will inherit a dependency on it that might also come with a negativity that they're unaware of the connection. Typically migraine or even depression.

I only drink water, eat pretty healthy but the only questionable thing I do is vape and there is no downfall if you can do it. Wonder how long until it becomes completely legal everywhere and war on drugs can end because a lot of people would be satisfied with just it.

Quote

10-13-2015 , 10:37 PM

#20264

ChrisV

Carpal \'Tunnel

Join Date: Jul 2004 Posts: 40,336

Quote:

Originally Posted by daveT

I tend to say that I prefer not to talk about whatever I was doing in my 20s, but it was nothing illegal.

This would be an instant no-hire if it was me doing the interview.

Quote

10-14-2015 , 06:00 AM

#20265

CyberShark93

veteran

Join Date: Dec 2013 Posts: 3,325

Lol, spent 8+hours everyday for a week optimising a program, only to find out ur friends version runs 3 times faster than urs

#sadface

Quote

10-14-2015 , 06:59 AM

#20266

CyberShark93

veteran

Join Date: Dec 2013 Posts: 3,325

also suppose I have a struct which looks like this

Code:

typedef struct {
    int nx;            /* no. of cells in x-direction */
    int ny;            /* no. of cells in y-direction */
    int max_iters;      /* no. of iterations */
    int reynolds_dim;  /* dimension for Reynolds number */
    float density;       /* density per link */
    float accel;         /* density redistribution */
    float omega;         /* relaxation parameter */
} param_t;

Code:

typedef struct {
    float speeds[9];
} speed_t;

Code:

    /* Allocate arrays */
    *cells_ptr = (speed_t*) malloc(sizeof(speed_t)*(params->ny*params->nx));
    if (*cells_ptr == NULL) DIE("Cannot allocate memory for cells");

and basically in each iteration of a loop i do something like

cells[iterator].speed[from 0 to 8]= somecalculation();

and I want to parallelise it s.t
thread1 does
cells[iterator].speed[from 0 to 8]= somecalculation();

and thread2 does
cells[iterator+1].speed[from 0 to 8]= somecalculation();

i thought false sharing wouldn't be happening because i expect cells[0] & cells[1] to be on different cache lines, however I am not entirely sure that this is the case. can someone please tell me how
the speed_t struct is stored in memory, is it essentially the same as cells[x][9]?

Quote

10-14-2015 , 07:42 AM

#20267

Wolfram

Carpal \'Tunnel

Join Date: Jan 2006 Posts: 15,066

Quote:

Originally Posted by CyberShark93

Lol, spent 8+hours everyday for a week optimising a program, only to find out ur friends version runs 3 times faster than urs

#sadface

it's the journey that matters, not the destination

Quote

10-14-2015 , 08:21 AM

#20268

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

Quote:

Originally Posted by Wolfram

it's the journey that matters, not the destination

only because by the time you arrive, your friend has been partying at the destination for three days, eaten all the food, and left without cleaning the mess. in fairness, the destination he saw was a breathtaking, exciting place, and way better than the journey!

Quote

10-14-2015 , 11:27 AM

#20269

numberonedonk

veteran

Join Date: Oct 2014 Posts: 2,181

Hello....

I want to get into app development (IOS specifically) and would also like to learn other programing languages.

At the moment I'm taking a IOS 9 /Swift course on Udemy but am not sure that is my best way to go about learning as some of the information seems quite vague or they don't explain why they are doing something.

I've looked around but there is so much different information/coding languages/ etc that I'm just unsure of where to start.

Thanks

Quote

10-14-2015 , 12:14 PM

#20270

Wolfram

Carpal \'Tunnel

Join Date: Jan 2006 Posts: 15,066

Have you considered going to college and getting a BS in comp. sci?

Quote

10-14-2015 , 12:18 PM

#20271

Roonil Wazlib

veteran

Join Date: Feb 2014 Posts: 3,333

alternatively, go to a college bookstore and see what books they use for classes you'd be interested in.

Get those books cheaper from amazon (or free elsewhere - some colleges put PDFs of their books online and let anyone download them) and go through at your own pace.

Yes you won't know what the prof thinks you should skip or focus on, but you also won't have 30 thousand dollars of debt.

Quote

10-14-2015 , 12:44 PM

#20272

numberonedonk

veteran

Join Date: Oct 2014 Posts: 2,181

Quote:

Originally Posted by Wolfram

Have you considered going to college and getting a BS in comp. sci?

I have not nor do I really want to go the whole college route. Take a few classes, sure. Get a degree, probably not. I will take a look at my local college to see what they offer though.

I know this is not even close to the same thing but would taking the MIT/Stanford computer science classes be a good place to start. To see if it's even something I would want to pursue?

Quote:

Originally Posted by Roonil Wazlib

So like my question above about the online courses, do you think a beginner computer science class would be a good place to start? I'm all about not spending $30k on a piece of paper if I can still learn.

Quote

10-14-2015 , 01:12 PM

#20273

Roonil Wazlib

veteran

Join Date: Feb 2014 Posts: 3,333

Yeah, starter course would be good.

Or grab a book used for starter courses and see if you can get through it. Most starter courses spend way the **** too much time on stuff like "this is an int, it's different than a char!" and way too little time spent on stuff like "this is how classes interact and do crazy interesting stuff!"

If you don't have a specific language in mind, I'd recommend Head First Java, which is well-written, very absorbable, but a little out of date. Will give you a good grasp of the basics of OO programming.

Quote

10-14-2015 , 02:31 PM

#20274

jjshabado

Carpal Tunnel

Join Date: Jul 2006 Posts: 22,732

Crypto Peeps:

If you generated a long salt (say 32 bytes) and hashed salt+value using md5 and then threw away the salt -> is it practically impossible to retrieve the original value?

(yes yes, I know md5 is bad, but thats not really the purpose of this question)