Is there anyway to make this C-code faster? - Page 4
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 4 of 4 FirstFirst 1234
Results 46 to 53 of 53

Thread: Is there anyway to make this C-code faster?

  1. #46
    Join Date
    Aug 2017
    Posts
    31

    Re: Is there anyway to make this C-code faster?

    ... 2kaud meant "xlng", not N.

  2. #47
    Join Date
    Aug 2017
    Posts
    31

    Re: Is there anyway to make this C-code faster?

    This might make sense for certain very sparse and very large graphs (think N=20000, Dens=0.1 )
    when typical xlng would be very long.

  3. #48
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,705

    Re: Is there anyway to make this C-code faster?

    Quote Originally Posted by mkh01 View Post
    >>no performance improvement can be obtained from having more threads then available cpus

    I would generally agree, but empirically I found the fastest speed occurs at NumThreads = 200*NumLogiclCpus
    ( but this is in my production code). I did not test this in the sample code I posted.
    My simplistic explanation is that some threads finish much faster than the others.
    In the test, thread 3 was used much less than the other threads. What these results don't say is the number of simultaneously executing threads - just the number that were used. I've changed post #42 to reflect this.

    PS. Although NumThreads is set to 1600 for my particular computer (8 CPU's), only 15 threads in total were actually created.
    Last edited by 2kaud; September 4th, 2017 at 12:19 PM. Reason: PS
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.3.4)

  4. #49
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,705

    Re: Is there anyway to make this C-code faster?

    Quote Originally Posted by mkh01 View Post
    This might make sense for certain very sparse and very large graphs (think N=20000, Dens=0.1 )
    when typical xlng would be very long.
    Which variant of the 'for loop' produces the best performance is likely to be different from small values of xlng to large values. The analysis in the posts in this thread re xlng is only for small values. For large xlng values, a variant that has a conditional termination test as part of the loop is likely to be faster. Further analysis would help to determine optimal method(s). See post #20 for an analysis of loop variations when xlng is 10000.
    Last edited by 2kaud; September 4th, 2017 at 01:16 PM.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.3.4)

  5. #50
    Join Date
    Aug 2017
    Posts
    31

    Re: Is there anyway to make this C-code faster?

    As a side note, this is very closely related to the "1000 Queen problem".
    Clay Math institute has a $1M prize on this (should be $1B really).
    In That problem N= 1,000,000 and Density = 0.999995

    See here:
    http://www.alphr.com/artificial-inte...-queens-puzzle
    Last edited by mkh01; September 4th, 2017 at 05:26 PM.

  6. #51
    Join Date
    Aug 2017
    Posts
    31

    Re: Is there anyway to make this C-code faster?

    First of all - enormous thanks! I achieved almost x2 speed improvement on large sparse graphs
    (N=12K, Density=0.1) without slowing down for average and dense graphs.

    There were 2 critical changes:

    1. I split the code for large and small xlng. On my PC this threshold is xlng>8 (about 20% speedup)
    2. In your loop with pointers, I replaced with indices and that was another 60% speedup.

    See the snippet below:
    Code:
                    //....................................................
            //    This construct is x2 faster on 12K.1 graphs
            //
            int r;
            for ( r=1; r<NumRem; r++ ) {
                int    re = Sfx[r];
                const PBYTE rConn = ConnectM(re);
            
                BYTE  cn = rConn[Xset[0]];
                for ( int i=1; i<xlng; i++ )
                    cn|= rConn[Xset[i]];
        
                if ( cn )    *Dst++ = re;
                else {
                    Xset[xlng++] = re;
                    if ( xlng>8 ) { r++; break; }
                }
            }
    
            for ( ;r<NumRem; r++ ) {
                int    re = Sfx[r];
                const PBYTE rConn = ConnectM(re);
            
                // BYTE  cn = 0;
                // for ( PVTC xp=Xset,Xend=Xset+xlng; xp!=Xend && !cn; cn = rConn[*xp++] );
    
                BYTE  cn = 0;
                for ( int i=0; i<xlng && !cn; cn = rConn[i++] );
                    
                if ( cn )    *Dst++ = re;
                else         Xset[xlng++] = re;
            }            
            //..................................................
    Last edited by mkh01; September 4th, 2017 at 05:41 PM.

  7. #52
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,705

    Re: Is there anyway to make this C-code faster?

    I achieved almost x2 speed improvement on large sparse graphs
    Great!

    In your loop with pointers, I replaced with indices and that was another 60% speedup.
    That's why analysis/profiling is needed to see what's happening on the computers used as post #33 shows that for my system pointers are faster!

    From the code in post #51, a couple of ideas that might slightly improve the loop - but for the number of times the loop is called, any small improvement could have a bigger overall effect.

    Code:
     for ( r=1; r<NumRem; r++ ) {
    Pre increment is faster than post increment. So unless post increment is needed, suggest that pre increment is always used. For integers etc this improvement is likely to be very little - but it all helps. This is because for post increment, a temp copy of the original value is made, then the value incremented and then the temp copy is used for the value. With pre increment this temp copy isn't needed as the value is directly incremented and then this new value is used.

    Code:
    for ( r=1; r<NumRem; ++r ) {
    and for all other places where the value is not used before increment.

    Code:
    int    re = Sfx[r];
    As the value of re is not changed, is re just used to avoid using Sfx[r] in the code? If yes, then in c++ re could be a ref. This means that the value of Sfx[r] isn't copied to re but re points to the same memory location as Sfx[r]. Consider

    Code:
    const auto    &re = Sfx[r];
    Note that the type of re and of Sfx has to be the same - no conversion is allowed - hence auto.
    Last edited by 2kaud; September 5th, 2017 at 04:23 AM.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.3.4)

  8. #53
    Join Date
    Aug 2017
    Posts
    31

    Re: Is there anyway to make this C-code faster?

    >>Note that the type of re and of Sfx has to be the same - no conversion is allowed - hence auto.[/QUOTE]

    Thanks again. I incorporated suggested changes. Code is looking more elegant now.

Page 4 of 4 FirstFirst 1234

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)