http://qs1969.pair.com?node_id=11143003


in reply to Re: checking a set of numbers for consistency mod p
in thread checking a set of numbers for consistency mod p

ahem, all your points were exactly what occurred to me on day 2 or so when I took closer look at hv's code/algorithm, though I understood nothing of maths involved. Indeed, looking at list "through modulo p" is looking at 2-d table with p columns. Then subsequent column extraction (and imagining a subset as table again, etc.) reduces amount of data, to inspect, exponentially. I don't know if it can be simpler or faster. I wrote some Perl, stared at it a little, and realized it's translatable to C almost line by line, my C skill would suffice. If data is not Perl array but packed bytes (e.g. 255 as undef), code is easily adjusted.

Lines marked //*/ were added only today to fix latest glitch mentioned. As I said, the whole thing was just code refactoring exercise on my part without understanding what's going on. And it certainly can be further improved. (edit: forgot END_OF_C when pasting; + better names for benchmark tests. edit 2: Aargh, sorry, it was before coffee in the morning, when I added today's //*/ lines and also "optimized" i.e. screwed bit tests in z_mask. Fixed.)

my @data = ( [ 2, [0, 1, 0, 2, 0]], [ 2, [1, 0, 5, 0, 1]], [ 2, [2, undef, undef, undef, 2]], [ 3, [1, 0, 0, 1, 0, 0, 1]], [ 2, [1, 0, 8, 0, 1]], [ 3, [undef, 0, 0, undef, 0, 0, 1]], [ 3, [undef, 0, 0, undef, 0, 0]], [ 3, [0, 1, undef, undef, 0, undef]], ); use Inline C => <<'END_OF_C'; int valid_set_c( int p, SV *a_ref ) { AV* array = (AV *)SvRV( a_ref ); int last = av_top_index( array ); int from = 0; int incr = 1; int initial_mask = ( 1 << p ) - 1; for ( int j = 0;; j ++ ) { int z_mask = initial_mask; int nz_cnt = 0; int nz_col; for( int i = from; i <= last; i += incr ) { SV* item = *av_fetch( array, i, 0 ); if ( SvOK( item )) { int col = i / incr % p; if ( SvIV( item ) == j ) { if ( nz_cnt && nz_col == col ) return 0; //*/ if ( z_mask & ( 1 << col )) { z_mask &= ~( 1 << col ); if ( !z_mask ) return 0; } } else { if ( nz_cnt ++ ) { if ( nz_col != col ) return 0; } else nz_col = col; if ( !( z_mask & ( 1 << nz_col ))) return 0; + //*/ } } } if ( nz_cnt <= 1 ) return 1; from += nz_col * incr; incr *= p; } } END_OF_C __END__ Rate valid_set valid_set_c valid_set 35669/s -- -89% valid_set_c 339083/s 851% --

Replies are listed 'Best First'.
Re^3: checking a set of numbers for consistency mod p
by hv (Prior) on Apr 16, 2022 at 21:14 UTC

    Nice stuff. :) It's a shame it will silently go wrong when p > 8 * sizeof(int), though. If you're lucky, the compiler may support declaring a variable-sized int[] array to save the bother of mallocing, but just indexing into it will already make the code a chunk more complex.

    And @LanX: there's no XS code here. The existence of Inline::C is the reason I never had to learn XS, and I'm very grateful for it. :)

      > And @LanX: there's no XS code here.

      This doesn't look like vanilla C

      > > SV* item = *av_fetch( array, i, 0 );

      Probably differing definitions of "XS" ?

      Cheers Rolf
      (addicted to the Perl Programming Language :)
      Wikisyntax for the Monastery

        SV* item = *av_fetch( array, i, 0 );

        I worry I'm simply being trolled, but: that looks absolutely like vanilla C to me. We're calling a function, passing it some arguments, getting back some sort of pointer-to-a-pointer, which we dereference and store in a new pointer variable. Clearly the function av_fetch() and the type SV will have been declared somewhere.

        The only magic here is an implicit #include <perl.h>, which brings in perl's standard typedefs, function declarations, etc. XS is a whole 'nother language that is parsed by its own compiler (xsubpp) rather than by a C compiler.

Re^3: checking a set of numbers for consistency mod p
by LanX (Saint) on Apr 16, 2022 at 19:52 UTC
    unfortunately I'm bad in reading C especially with interspersed XS. :(

    But probably performance would benefit from copying the Perl array to a C array first?

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    Wikisyntax for the Monastery