14

I've been running into code (new code) that uses what I call 'Parallel Arrays' or Lists. Meaning there are 2 arrays that contain related data and are linked by their position (index) in the array.

I consider this confusing and prone to all sorts of errors. The solution I normally propose is to create an object called Company with the fields CompanyId and CompanyName.

An very real example:

List<string> companyNames;
List<int> companyIds;

//...They get populated somewhere and we then process

for(var i=0; i<companyNames.Count; i++)
{
    UpdateCompanyName(companyIds[i],companyNames[i]);
}

Are these parallel arrays considered bad practice?

  • 9
    Simply further proof that no language has been invented in which you cannot write Fortran. – andy mango Jun 2 '17 at 0:01
  • 3
    There can be (quite significant) caching benefits to doing something like this (though you need contiguous arrays not linked lists), and this has become somewhat popular in game programming related to "data-oriented design". However, this does not seem to apply to your case. It doesn't look like you are making performance critical code. – Derek Elkins Jun 2 '17 at 0:28
  • 2
    @DerekElkins ... Interesting that your comment follows one comparing this to Fortran code. Early versions of Fortran lacked support for user defined structures, and even after it was added idiomatic Fortran code uses multiple arrays of properties not arrays of structures. And this is often credited as part of the reason Fortran is often considered to be the fastest language. – Jules Jun 2 '17 at 17:05
  • 3
    A thought tangential to this question: many functional languages actively encourage working with such lists. They have a function, usually called zip, that converts them to a list of tuples. Your code looks like C#. The latest version of C# has added support for first class tuples. I wonder if, therefore, they have added a zip function somewhere that could put your lists into a useful structure for you automatically? – Jules Jun 2 '17 at 17:20
  • 4
    Well, there are sometimes reasons for using two arrays intentionally, but in 99% of all cases I have seen this, the only reason for it was the lazyness of the original author to introduce an embracing data structure. – Doc Brown Jun 3 '17 at 10:49
23

Here are some reasons why someone might use parrel arrays:

  1. In a language that does not support classes or structs
  2. To avoid thread locking when individual threads are only modifying one of the columns
  3. When the persistence method forces these things to be stored separately and you are reconstituting them.
  4. They can consume less memory if the structures are padded. (not applicable for these data types in C#)
  5. When parts of the data need to be kept close together to make efficient use of the CPU cache (would not be of help in the above code).
  6. Use of Single Instruction Multiple Data (SIMD) op codes. (not applicable for this code, or strings at all)

I do not see any compelling reason to do this in this case... and there are likely better options in all of the above or are not so useful in a high level language.

  • 3
    They can consume less memory as well if the structures are padded. Several large arrays, allocated intelligently, can consume less memory than an array of structures. – Frank Hileman Jun 1 '17 at 23:58
  • 4
    4. When parts of the data need to be kept close together to make efficient use of the CPU cache. (Necessary in rare cases.) – Blrfl Jun 2 '17 at 1:12
  • @Frank Hileman, Whilie I think that the answer by TheCatWhisperer is completely correct, your comment is, actually, the best reason to choose this approach. If the memory consumption is critical, memory overhead on structs padding can be significant, especially if large numbers are in play. – Vladimir Stokic Jun 2 '17 at 7:45
  • Added your suggestions to the answer – TheCatWhisperer Jun 2 '17 at 16:53
  • Re (2), How's that? I can write a program with a single array of structs and a lock per field just as easily as I can write one with multiple arrays and a lock per array. – Solomon Slow Jun 7 '17 at 18:53
7

I've been guilty of using parallel arrays. Sometimes you're head's into the structure so much you don't want to think about how to abstract it. Abstraction can be a little harder to refactor so you're reluctant to launch right into it until you've proven what you really need.

At that point though it's worth considering refactoring to abstract away the details. Often the biggest reason I'm reluctant to do it turns out to be that it's hard to think of a good name.

If you can see a good way to abstract parallel arrays away do it every time. But don't paralyze yourself by refusing to touch them. Sometimes a little dirty code is the best stepping stone to great code.

6

This pattern is sometimes also called Structure of Arrays (as opposed to Array of Structures), and is extremely useful when vectorizing code. Rather than writing a calculation that runs on a single structure and vectorizing bits of it, you write the calculation as you normally would, except with SSE intrinsics so that it runs on 4 structures instead of one. This is usually easier, and almost always faster. The SoA format makes this very natural. It also improves alignment, which makes the SSE memory operations faster.

  • Yes, this approach is used when doing machine learning on the GPU. It's customary to pull apart the fields of many separate examples, pack all the values of each field into a separate tensor, and pass those tensors along to be computed on in bulk to produce a list of predictions. – Reinstate Monica Jun 7 '17 at 18:32

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.