Large LOGICAL arrays

WSinc · ‎07-13-2012

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.

Steven_L_Intel1 · ‎07-13-2012

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.

JVanB · ‎07-14-2012

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

[fortran]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 [/fortran]
With output
[plain]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 [/plain]

jimdempseyatthecove · ‎07-15-2012

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

Jim

WSinc · ‎07-16-2012

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......

jimdempseyatthecove · ‎07-17-2012

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

JVanB · ‎07-17-2012

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.

SergeyKostrov · ‎07-18-2012

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

John_Campbell · ‎07-18-2012

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