0

I am usually a Python / Database programmer, and I am considering using C for a problem.

I have a set of sequences, 8 characters long with 4 possible characters. My problem involves combining sets of these sequences and filtering which sets match a criteria. The combinations of 5 run into billions of rows and takes around an hour to run.

So I can represent each sequence as 2 bytes.

If I am working on a 64 bit architechture will I gain any advantage by keeping these data structures as 2 bytes when I generate the combinations, or will I be as well storing them as 8 bytes / double ? (64 bit = 8 x 8)

If I am on a 64 bit architecture, all registers will be 64 bit, so in terms of operations that shouldn´t be any faster (please correct me if I am wrong).

Will I gain anything from the smaller storage requirements - can I fit more combinations in memory, or will they all take up 64 bits anyway?

And finally, am I likley to gain anything coding in C. I have a first version, which stores the sequence as a small int in a MySQL database. It then self joins the tabe to itself a number of times in order to generate all the possible combinations. The performance is acceptable, depending on how many combinations are generated. I assume the database must involve some overhead.

  • Maybe some kind of tree structure could be used to order the sequences which would facilitate searching for a match. – CWallach Oct 18 '13 at 18:30
  • I am looking at various approaches to solving this one. I expect the final solution will involve many of them. Even if I don use the C approach I would love if people explained how the 64 bit / 8 bit stuff works for my curiosity as much as anything! – wobbily_col Oct 18 '13 at 18:48
  • 1
    I don't really understand the question. An array of 16 bit values will typically be allocated without wasted space. There may be a small performance penalty for reading a 16 bit value that isn't aligned on a 64-bit boundary. – CWallach Oct 18 '13 at 19:32
  • @CWallach: I guess that's the point, this fact seems to be obvious for you but not for the OP, he seems to believe an array of 16 bit values will strangely need 64 bits of storage for each array entry. – Doc Brown Oct 19 '13 at 13:30
2

If I am working on a 64 bit architechture will I gain any advantage by keeping these data structures as 2 bytes when I generate the combinations, or will I be as well storing them as 8 bytes / double ? (64 bit = 8 x 8)

Squeezing your data into 2 bytes instead of 8 will obviously reduce the amount of memory needed for large arrays of these sequences to ~1/4. This fact is mostly independent of your processor architecure, regardless of beeing 64, 32, 16 or just 8 bit.

If this will result in any measurable performance improvement, depends if the packed representation of the amount of data you are going to process "in a whole" will fit completely into faster memory (for example, main memory), while the unpacked representation does not (for example, you will need external hard disk space for it).

Honestly, since you did not provide any details about how your "filtering" does look like, it is unclear if you need to unpack the data first before you can process it further, which may use up additional computing time. Or the difference in your case may show up beeing so small that the packing is fully unnecessary. So, what you have to do here is: try and measure, measure, measure!

  • OK, so if I use C, (or Numpy) then it will be beneficial to store everything as small as possible. FIltering is done using bitwise operators to calculate hamming distance. I already packed the data into small ints so that the filtering can be done as quickly as possible. Just wondering how much benefit I wil get from taking it out of the database now. – wobbily_col Oct 21 '13 at 18:38
  • @wobbily_col: no, in general it will not beneficial to store everything as small as possible, only if the circumstances are like the ones I described in my answer - was I really so unclear? – Doc Brown Oct 21 '13 at 22:32
1

You are likely to optimize for the wrong case. Remember the two golden rules of optimization:

  1. Premature optimization is the root of all evil.
  2. No optimizing without profiling.

As 48 = 65536 is significantly less than your ”billions of combinations”, I doubt you are going to run into performance issues regardless of the programming language you are using. Have you prototyped this in Python? Is it not fast enough? If you do want to optimize that, try to find an algorithm that doesn't even create unwanted combinations.

The advantage of representing a single combination as an integer (for now, size is irrelevant), is that you can iterate through all combinations by simply incrementing that integer. This is going to be fast regardless of language. Note that floating point numbers are not useful here! In C, you could use an uint16_t or larger in this scenario. You need a separate termination condition regardless of the type you are using.

How many bits any type actually takes up in memory is subject to alignment. You should only worry about this after re-reading the two above optimization rules, because your compiler will know more about alignment than you.

  • The sequences are combinations of 4 characters, 8 chars long. I want to combine say 5 of them together and check if it meets criteria. I have 222 unique sequences, and combined them in mysql, and over a billion are meeting the criteria. – wobbily_col Oct 18 '13 at 17:37
  • @wobbily_col So you are saying you are actually interested in all combinations of 5 8-char strings? That would be over 4^(8·5) > 1·10^24 different combinations – too much to go through (representing one combination would need 80 bit). You need to find a shortcut to avoid brute-forcing this. – amon Oct 18 '13 at 17:46
  • Yes, I am looking at combinations. I am well aware that the number get huge - and I am looking at filtering options before combining, but I see that as a different aspect of the overall problem. I was hoping people could answer my questions about memory useage on a 64 bit architecture. I am interested in learning about such things. – wobbily_col Oct 18 '13 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.