S
Schraalhans Keukenmeester
I have a substantial random stream of (numerical, long int) data (coming
from several SCADA sources) that needs to be passed thru a function that
tallies the occurrences of several different bit patterns in each number
(or in fact 32 bit row, of which a few (leftmost) are bogus).
Speediness of execution is high on the priority list.
I thought of a solution along these lines, avoiding relatively slow
switch/case or several if/elseif combinations:
If the data would have been short (or int) I'd be able to do this:
#include <stdio.h>
#define BOGUS_BIT_MASK SHORT_MAX & (SHORTMAX >> 3)
//assume 3 bogus bits in case we use short
#define BATCH_SIZE 1024
typedef unsigned long long ull;
typedef FILE* fileptr;
ull frequency[SHORT_MAX];
int batch[BATCH_SIZE];
fileptr stream;
void tally (const ull batch[], const int batch_size, int freq[]);
void zero_freq (ull freq);
int getdata (int batch[], const int BATCH_SIZE, const fileptr fp);
int main (void)
{
// zero all cells in frequency array (omitted)
while (getdata(batch,BATCH_SIZE,stream)){
// function definition omitted here
tally (batch,BATCH_SIZE,frequency);
}
process_results (frequency);
// function definition omitted here
return 0;
}
void tally (const ull batch[], const int batch_size, int freq[]);
{
int i;
for(i=0;i<batch_size;i++) {
freq[batch & BOGUS_BIT_MASK & BIT_PATTERN_01]++;
freq[batch & BOGUS_BIT_MASK & BIT_PATTERN_02]++;
freq[batch & BOGUS_BIT_MASK & BIT_PATTERN_03]++;
freq[batch & BOGUS_BIT_MASK & BIT_PATTERN_04]++;
// etc. etc. in reality bitpatterns will be stored in an array
// and bogus mask is applied once each run of the loop.
}
}
Unfortunately, with int32 data using a mostly empty array of the desired
size (largest bitpattern value comes pretty close to 2**29) is
challenging, if not impossible on a given machine/os.
In total, it's likely up to a few hundred bitpatterns may be used, but I
can't guarantee yet it won't expand later.
I quickly abandoned the if/then approach, as it became obvious it would
result in a messy, slow, hard to debug/adapt spaghetti.
Has anyone got a better idea for the huge array ? Is there an easy (to
maintain) way of squeezing out all the non-used cells in the array? Some
kind of mapping perhaps ? I tried figuring out a list approach, but that
more or less stranded. Besides I could not see an easy way to target the
right chain in the list in a way similar to the array approach. If
indeed my approach deserves further developing, do you expect a big
further speed gain from coding the taly function in a OS-specific ASM
version? I know this is platform specific, just like to get a feel of
what your opninions are on how succesful modern compilers are in optimizing.
I am fully aware I may be completely off on the wrong foot here, in
which case I am glad to be steered in the right direction. Please don't
let a possible typo in above semi-code put you off, it's not the real
thing, as it still is in experimental stage, rather more complicated,
partly handed to my by others, and messy and illegible as hell.
Thanks for your help in advance, much appreciated.
Sh.
PS in case you're interested, the final program will be put to use as
data hub for an (in-house developed) logistics planning package and
feedback to both SCADA devices and an accounting database. All efforts
sofar have stranded, now I am asked to burn my fingers... Interesting
yet challenging.
from several SCADA sources) that needs to be passed thru a function that
tallies the occurrences of several different bit patterns in each number
(or in fact 32 bit row, of which a few (leftmost) are bogus).
Speediness of execution is high on the priority list.
I thought of a solution along these lines, avoiding relatively slow
switch/case or several if/elseif combinations:
If the data would have been short (or int) I'd be able to do this:
#include <stdio.h>
#define BOGUS_BIT_MASK SHORT_MAX & (SHORTMAX >> 3)
//assume 3 bogus bits in case we use short
#define BATCH_SIZE 1024
typedef unsigned long long ull;
typedef FILE* fileptr;
ull frequency[SHORT_MAX];
int batch[BATCH_SIZE];
fileptr stream;
void tally (const ull batch[], const int batch_size, int freq[]);
void zero_freq (ull freq);
int getdata (int batch[], const int BATCH_SIZE, const fileptr fp);
int main (void)
{
// zero all cells in frequency array (omitted)
while (getdata(batch,BATCH_SIZE,stream)){
// function definition omitted here
tally (batch,BATCH_SIZE,frequency);
}
process_results (frequency);
// function definition omitted here
return 0;
}
void tally (const ull batch[], const int batch_size, int freq[]);
{
int i;
for(i=0;i<batch_size;i++) {
freq[batch & BOGUS_BIT_MASK & BIT_PATTERN_01]++;
freq[batch & BOGUS_BIT_MASK & BIT_PATTERN_02]++;
freq[batch & BOGUS_BIT_MASK & BIT_PATTERN_03]++;
freq[batch & BOGUS_BIT_MASK & BIT_PATTERN_04]++;
// etc. etc. in reality bitpatterns will be stored in an array
// and bogus mask is applied once each run of the loop.
}
}
Unfortunately, with int32 data using a mostly empty array of the desired
size (largest bitpattern value comes pretty close to 2**29) is
challenging, if not impossible on a given machine/os.
In total, it's likely up to a few hundred bitpatterns may be used, but I
can't guarantee yet it won't expand later.
I quickly abandoned the if/then approach, as it became obvious it would
result in a messy, slow, hard to debug/adapt spaghetti.
Has anyone got a better idea for the huge array ? Is there an easy (to
maintain) way of squeezing out all the non-used cells in the array? Some
kind of mapping perhaps ? I tried figuring out a list approach, but that
more or less stranded. Besides I could not see an easy way to target the
right chain in the list in a way similar to the array approach. If
indeed my approach deserves further developing, do you expect a big
further speed gain from coding the taly function in a OS-specific ASM
version? I know this is platform specific, just like to get a feel of
what your opninions are on how succesful modern compilers are in optimizing.
I am fully aware I may be completely off on the wrong foot here, in
which case I am glad to be steered in the right direction. Please don't
let a possible typo in above semi-code put you off, it's not the real
thing, as it still is in experimental stage, rather more complicated,
partly handed to my by others, and messy and illegible as hell.
Thanks for your help in advance, much appreciated.
Sh.
PS in case you're interested, the final program will be put to use as
data hub for an (in-house developed) logistics planning package and
feedback to both SCADA devices and an accounting database. All efforts
sofar have stranded, now I am asked to burn my fingers... Interesting
yet challenging.