Is an Array of Derived Type with CHARACTER(:), ALLOCATABLE Contiguous?

[Scott_Boyce]

This is more of a general question that I was pondering over designing a CHARACTER array in terms of efficiency of access for faster runtime.

In particular, I am building an array that is meant to have variable length CHARACTER types.

That is something like:
(I'm writing this on the fly quickly so it may contain minor bugs)

character(:), dimension(:), allocatable:: example_char

but would allow for different length characters for each dimension.

One thought is to just make derived data type as:

type CharTyp
  character(:), allocatable:: str
end type

type(CharTyp), dimension(:), allocatable:: ch

then each record of str can be variable length.

My first question is, under the hood is the compiler just treating str as a pointer for allocating the memory so there is no contiguous memory benefit within the greater dimensional array? That is doing something like:

allocate(ch(5))
ch(1)%str = "a"
ch(2)%str = "ab"
ch(3)%str = "abc"
ch(4)%str = "abcd"
ch(5)%str = "abcde"

do i=1, 5
  write(*,*) ch(i)%str
end do

would have the loop going through ch and jumping to memory to find each str. I get that str implies contiguous because its not a pointer, but then is a pointer with regards to ch and not stored in contiguous memory? That is the loop, is jumping around in memory.

A thought I had that may be faster is to use something like a regular character but reserve the first two bytes as an unsigned integer of the length (max size then is 65,535).

For example:

character(:), dimension(:), allocatable:: string
allocate(character(256):: string(5))

! First two bytes are string size and then 2: is the actual string.
! In practical terms I probably have to have something that does int32 to 2 byte char
string(1) = transfer(1_int16, "  ") // "a"
string(2) = transfer(2_int16, "  ") // "ab"
string(3) = transfer(3_int16, "  ") // "abc"
string(4) = transfer(4_int16, "  ") // "abcd"
string(5) = transfer(5_int16, "  ") // "abcde"

do i=1, 5
  j = transfer(string(:2), j) + 2
  !
  write(*,*) string(i)(3:j)
end do

In this example, the entire array would have to be reallocated if the string needed be longer than 256, but its at least stored in contiguous memory.

As a general discussion, would be better in terms of speed to use character arrays with the same len, or to go the route of a derived data type with different allocated character lengths.

To me it would seem that the code would be faster looping through an array with all the same character lengths, even if only small strings (say len=4) were stored within the larger string (len=256).

Thanks for everyone thoughts.

[Steve_Lionel]

You're forced to do this with a derived type, as shown in your second snippet. ch will be an array of descriptors, each containing pointer and length information for each instance of str. There's no guarantee of contiguity between any of the various str components (and indeed it is unlikely.) 

My usual advice is to write what makes the most sense from a readability and maintainability standpoint. Measure the performance of the application, and if it needs improvement, use VTune or similar to see where the time is being spent. I recommend against trying to micro-optimize here. Use the language features that are there (deferred-length allocatable) and don't try to roll your own.

[Scott_Boyce]

@Steve_LionelI tend to get a bit obsessed with micro-opts. Mostly cause I work with a lot of numerical codes and usually these kind of designs are what I use in hash tables or something that is called millions of times. The hope is that once the derived data type is validated and really optimized, the source code itself is not looked at again.

Right now I was looking at some of my old hash table code that has a each record key_val and the hash table is kv:

  type key_val
      character(:), allocatable:: key
      character(:), allocatable:: val
  end type

  type(key_val), dimension(:), allocatable:: kv

I was debating on refactoring it into two separate arrays (key and val) and if I should ditch the allocatable character:

character(256), dimension(:), allocatable:: key
character(256), dimension(:), allocatable:: val

! or even just doing (its not valid Fortran but a function coud do this)

character(256), dimension(:, 2), allocatable:: kv

The idea with the hash is to have O(1) index performance, but I use a rolling index to handle collisions (use subsequent unused indices until an open slot is found), so it has to quickly move through the vector once a starting index is found.

[Steve_Lionel]

There is the issue of AOS vs. SOA (Arrays of Structures vs. Structures of Arrays). Which is better depends on typical memory access.  What you don't see when you use allocatables is the storage taken up by the descriptor, which is likely to be larger than the string itself, though I don't know how long your strings are.  If they're all reasonably short (say, under 32 bytes), then use fixed-length strings rather than allocatable. If some are longer you could do something clever to indicate that the string is actually a C_PTR and length combo (say, first eight bytes are zero).