Re^5: Odometer pattern iterator (in C).

I'm still brushing the rust off my C. :) This one is 50% faster with only slight tweaks. This tight loop is *highly* sensitive to almost any change. BTW, going from -o2 to -o4 doubles speed.

// inc_c - http://perlmonks.org/?node_id=1128230
// 8.52 secs. for 16/32 count=601080390 -o2
// 3.16 secs. for 16/32 count=601080390 -o4

#include <stdlib.h>
#include <stdio.h>

#define N 16 // number of elements wanted
#define M 32 // place

static int place[N+1];
static int count = 0;

int
step(void)
  {
  int *p = place;

  for(int i = 0; i < N; i++, p++ )
    {
    if(*p < p[1] - 1)
      {
      ++*p;
      while( --i >= 0 ) *--p -= place[0];
      return 1;
      }
    }
  return 0;
  }

int
main(int argc, char **argv)
  {
  int i;
  int more = 1;

  for(i = 0; i < N; i++) place[i] = i;
  place[N] = M;

  while( more )
    {
    //for(i = 0; i < N; i++) printf(" %d", place[i]);
    //putchar('\n');
    count++;
    more = step();
    }

  printf("%d\n", count);

  exit(0);
  }
[download]

Comment on Re^5: Odometer pattern iterator (in C). Download Code

Replies are listed 'Best First'.
Re^6: Odometer pattern iterator (in C). by BrowserUk (Patriarch) on May 30, 2015 at 02:18 UTC
Yes. That now beats the A::C version by about 20% (6.5s v 8) on my system when compiled with /Ox. Thank you. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply]
Re^7: Odometer pattern iterator (in C). by Anonymous Monk on May 30, 2015 at 03:03 UTC
Slightly faster. It's getting too silly, though. However, the step function is getting smaller due to better understanding of the problem. // inc_c - http://perlmonks.org/?node_id=1128230 // 8.52 secs. for 16/32 count=601080390 -O2 // 3.08 secs. for 16/32 count=601080390 -O3 #include <stdlib.h> #include <stdio.h> #define N 16 // number of elements wanted #define M 32 // place static int place[N+1]; static int count = 0; int step(void) { int p = place; for(int i = 0; i < N; p++ = i++ ) { if(p < p[1] - 1) { ++p; return 1; } } return 0; } int main(int argc, char **argv) { int i; int more = 1; for(i = 0; i < N; i++) place[i] = i; place[N] = M; while( more ) { //for(i = 0; i < N; i++) printf(" %d", place[i]); //putchar('\n'); count++; more = step(); } printf("\ncount %d\n", count); exit(0); } [download] Thanks for the opportunity to scrape some rust off my C skills :)	[reply] [d/l]
Re^8: Odometer pattern iterator (in C). by BrowserUk (Patriarch) on May 30, 2015 at 08:13 UTC
Slightly faster. It's getting too silly, though. Consistenly another 25% (5s v 6.5s). Indeed. your gains are now going to be constrained by the efficiency of the other code in the main loop that uses the generated indices. Thanks for the opportunity to scrape some rust off my C skills :) Thanks for taking that opportunity. The way you've folded the inner and outer loop (from the A::C version) together, makes the requirements of the algorithm far clearer, and as you said, that's key. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply]
Re^8: Odometer pattern iterator (in C). by tybalt89 (Monsignor) on Dec 30, 2016 at 21:50 UTC
Posted before I joined. Adding for "Nodes You Wrote"	[reply]
Re^7: Odometer pattern iterator (in C). by Anonymous Monk on May 30, 2015 at 02:26 UTC
I'm still tweaking it - there may be more to come :)	[reply]


There's more than one way to do things
	PerlMonks