# Large LOGICAL arrays

## Large LOGICAL arrays

I was wondering if there is a way to take advantage of the
fact that LOGICALS are eithrTRUE or FALSE. That only takes up one bit of storage.
The smallest LOGICAL we can have is 8 bits, i.e. LOGICAL*1. Why can't Fortran
have a bit-wise LOGICAL variable?

This would save a lot of space for very large LOGICAL arrays.

Or maybe there is a convenient way to accomplish the same thing?

I currently use BIT-wise functions like IBITS, etc. but that gets rather awkward.

9 posts / 0 new
For more complete information about compiler optimizations, see our Optimization Notice.

There have been proposals to add a "bit" type to the language, but it didn't get enough votes. The bitwise intrinsics were deemed an adequate substitute.

Steve

One might say that the bitwise intrinsics weren't deemed adequate so they were augmented in further editions of the standard. Consider the following example where a set of equivalent logical expressions are written out in logical form, then in bitwise form. The new bitwise syntax added in f2003 and f2008 make the code more readable than earlier standards would allow

```program bit_test

call logical_test

call bitwise_test

end program bit_test
subroutine logical_test

implicit none

logical A(16), B(16), C(16), D(16)

logical f1(16), f2(16), f3(16), f4(16)

integer i, j
A = [(.FALSE., i = 1, 8), (.TRUE., i = 1, 8)]

B = [([(.FALSE., i = 1, 4), (.TRUE., i = 1, 4)], j = 1, 2)]

C = [(.FALSE., .FALSE., .TRUE., .TRUE., i = 1, 4)]

D = [(.FALSE., .TRUE., i = 1, 8)]

! Canonical sum of products form

f1 = (.NOT.A .AND.      B .AND. .NOT.C .AND. .NOT.D) .OR. &

(.NOT.A .AND.      B .AND. .NOT.C .AND.      D) .OR. &

(     A .AND. .NOT.B .AND. .NOT.C .AND.      D) .OR. &

(     A .AND. .NOT.B .AND.      C .AND.      D) .OR. &

(     A .AND.      B .AND. .NOT.C .AND. .NOT.D) .OR. &

(     A .AND.      B .AND. .NOT.C .AND.      D) .OR. &

(     A .AND.      B .AND.      C .AND.      D)

! Canonical product of sums form

f2 = (     A .OR.      B .OR.      C .OR.      D) .AND. &

(     A .OR.      B .OR.      C .OR. .NOT.D) .AND. &

(     A .OR.      B .OR. .NOT.C .OR.      D) .AND. &

(     A .OR.      B .OR. .NOT.C .OR. .NOT.D) .AND. &

(     A .OR. .NOT.B .OR. .NOT.C .OR.      D) .AND. &

(     A .OR. .NOT.B .OR. .NOT.C .OR. .NOT.D) .AND. &

(.NOT.A .OR.      B .OR.      C .OR.      D) .AND. &

(.NOT.A .OR.      B .OR. .NOT.C .OR.      D) .AND. &

(.NOT.A .OR. .NOT.B .OR. .NOT.C .OR.      D)

! Optimized sum of products form

f3 = (B .AND. .NOT.C) .OR. (A .AND. D)

! Optimized product of sums form

f4 = (B .OR. D) .AND. (A .OR. B) .AND. &

(A .OR. .NOT.C) .AND. (.NOT.C .OR. D)

write(*,'(a)') 'Truth Table for Logical Test'

write(*,'(4(1x,a1),4(1x,a2))') 'A','B','C','D','f1','f2','f3','f4'

write(*,'((4(1x,L1),4(2x,L1)))') (A(i),B(i),C(i),D(i), &

f1(i),f2(i),f3(i),f4(i),i=1,16)

end subroutine logical_test
subroutine bitwise_test

implicit none

integer A, B, C, D

integer f1, f2, f3, f4

integer i
A = int(Z'FF00')

B = int(Z'F0F0')

C = int(Z'CCCC')

D = int(Z'AAAA')

! Canonical sum of products form

f1 = iany([ &

iall([NOT(A),     B , NOT(C), NOT(D)]), &

iall([NOT(A),     B , NOT(C),     D ]), &

iall([    A , NOT(B), NOT(C),     D ]), &

iall([    A , NOT(B),     C ,     D ]), &

iall([    A ,     B , NOT(C), NOT(D)]), &

iall([    A ,     B , NOT(C),     D ]), &

iall([    A ,     B ,     C ,     D ])])

! Canonical product of sums form

f2 = iall([ &

iany([    A ,     B ,     C ,     D ]), &

iany([    A ,     B ,     C , NOT(D)]), &

iany([    A ,     B , NOT(C),     D ]), &

iany([    A ,     B , NOT(C), NOT(D)]), &

iany([    A , NOT(B), NOT(C),     D ]), &

iany([    A , NOT(B), NOT(C), NOT(D)]), &

iany([NOT(A),     B ,     C ,     D ]), &

iany([NOT(A),     B , NOT(C),     D ]), &

iany([NOT(A), NOT(B), NOT(C),     D ])])

! Optimized sum of products form

f3 = ior(iand(B, NOT(C)), iand(A, D))

! Optimized product of sums form

f4 = iall([ior(B, D), ior(A, B), ior(A, NOT(C)), ior(NOT(C), D)])

write(*,'(/a)') 'Truth Table for Bitwise Test'

write(*,'(4(1x,a1),4(1x,a2))') 'A','B','C','D','f1','f2','f3','f4'

write(*,'((4(1x,L1),4(2x,L1)))') &

(BTEST([A,B,C,D,f1,f2,f3,f4],i),i=0,15)

end subroutine bitwise_test

```

With output
```Truth Table for Logical Test

A B C D f1 f2 f3 f4

F F F F  F  F  F  F

F F F T  F  F  F  F

F F T F  F  F  F  F

F F T T  F  F  F  F

F T F F  T  T  T  T

F T F T  T  T  T  T

F T T F  F  F  F  F

F T T T  F  F  F  F

T F F F  F  F  F  F

T F F T  T  T  T  T

T F T F  F  F  F  F

T F T T  T  T  T  T

T T F F  T  T  T  T

T T F T  T  T  T  T

T T T F  F  F  F  F

T T T T  T  T  T  T
Truth Table for Bitwise Test

A B C D f1 f2 f3 f4

F F F F  F  F  F  F

F F F T  F  F  F  F

F F T F  F  F  F  F

F F T T  F  F  F  F

F T F F  T  T  T  T

F T F T  T  T  T  T

F T T F  F  F  F  F

F T T T  F  F  F  F

T F F F  F  F  F  F

T F F T  T  T  T  T

T F T F  F  F  F  F

T F T T  T  T  T  T

T T F F  T  T  T  T

T T F T  T  T  T  T

T T T F  F  F  F  F

T T T T  T  T  T  T

```

Have you considered that the memory cost of accessing a bit may exceed the 7-bits when accessing the byte?

Jim

Blog: The Parallel Void

Well, if I had 32,000,000 logicals to test, I would pack them in 32 bits per integer*4 word.
So it is like a 32 by 1000000 bit array.
But the logic for testing that can be tricky......

Quoting billsincl Well, if I had 32,000,000 logicals to test, I would pack them in 32 bits per integer*4 word.
So it is like a 32 by 1000000 bit array.
But the logic for testing that can be tricky......

When these are in an array (iow accessed via index) then you can use the current bit functions encased in access routines that you write. However, if these are individually named and accessed by individual statements, then the program size would be larger than the 7 bits saved per variable and execution time longer. 32MB is <1% of memory on a typical desktop or notebook.

Now then when these flags are used as arrays, then searching a bit array can be much faster as you can test 64 bits at one time.

Jim Dempsey

Blog: The Parallel Void

It's not as simple as that. If the data compression results in multiple hits per cache line accessed, the program will be faster, even with more code to process each bit. For example, if the array is mostly swept through sequentially, it would be roughly 8X faster.

Quoting billsincl ...Or maybe there is a convenient way to accomplish the same thing?

I currently use BIT-wise functions like IBITS, etc. but that gets rather awkward.

Even in a lower level programminglanguages, like C or C++, there is no a native support for 'bitset's. A widely
used STL library has a 'bitset' class and I wouldn't call it as"awkward".However, when a variable of the'bitset' type is
declared it has some number of unused bits andthis is by design of the 'bitset' class.I don't knowwhy it was done
byHP software developers.

Best regards,
Sergey

An alterrnative is to manage the storage of a large 2D virtual logical array with interface routines, such as:
get_logical(ix,iy) (logical function)
set_logical(ix,iy), (subroutine or function)
active_logical(ix,iy), (logical function) or
is_logical(ix,iy) (logical function)

These routines could be used to do all the bit manipulation that is required in a compacted LOGICAL*4 vector. While they might be a bit slower, they would use 1/8 of LOGICAL*1 or 1/32 of LOGICAL*4 storage. If the size is significant, as implied, then the saving in virtual memory could be emmense.
These routines would be idealy suited to a contains module.

Recently I used a similar approach for a project wherea virtual 2D derived type array would have been about 120gb in size. By managing it, converting array(ix,iy) > page(jx,jy,ipage) > derived_type_list(k).I reduced the size to about 800mb of data stored, with asignificant reduction in computation, by recognising the sparcity of the data. The overhead of referencing or setting values, via theseroutines was not noticeable. The resulting code to access the data changed little from using array addresses to function calls.

John