2,951
edits
Boolean: Difference between revisions
Jump to navigation
Jump to search
→Boolean optimization: Incomplete list of APLs with bit Booleans
mNo edit summary |
(→Boolean optimization: Incomplete list of APLs with bit Booleans) |
||
| Line 84: | Line 84: | ||
== Boolean optimization == | == Boolean optimization == | ||
Optimizing for Boolean arrays is one special case of using a small [[internal type]] in order to reduce memory usage and improve speed in an APL interpreter. For Booleans this optimization is particularly valuable because each Boolean is representable with a single bit—the smallest discrete quantity available on a CPU. The decision to use packed arrays with eight Booleans for each byte was made by [[Larry Breed]] in [[APL\360]], even though the IBM System/360 did not have the capability to address individual bits. | Optimizing for Boolean arrays is one special case of using a small [[internal type]] in order to reduce memory usage and improve speed in an APL interpreter. For Booleans this optimization is particularly valuable because each Boolean is representable with a single bit—the smallest discrete quantity available on a CPU. The decision to use packed arrays with eight Booleans for each byte was made by [[Larry Breed]] in [[APL\360]], even though the IBM System/360 did not have the capability to address individual bits. Later APLs implemented with bit Booleans include [[APL\3000]], [[SHARP APL]], [[Dyalog APL]], and [[dzaima/APL]]. | ||
Packed Booleans are especially valuable in array languages because only arrays of Booleans are subject to this optimization: a single Boolean in a processor will use an entire register just like an integer or floating-point value. Using a packed representation for arrays of Booleans both decreases memory usage by a factor of eight and makes faster algorithms possible, as eight times more one-bit values may be fit in a single CPU register (and thus manipulated at once) than one-byte values. However, packed Boolean arrays have a drawback: while optimized algorithms on bit Booleans are usually faster than those on byte Booleans, packed Boolean algorithms are often considerably harder to implement, and unoptimized algorithms using bit Booleans tend to be slower. This is because bits in memory cannot be addressed directly on a modern computing architecture. To read or write a single bit at an arbitrary offset, the byte containing it must be read and then the appropriate bit picked out. | Packed Booleans are especially valuable in array languages because only arrays of Booleans are subject to this optimization: a single Boolean in a processor will use an entire register just like an integer or floating-point value. Using a packed representation for arrays of Booleans both decreases memory usage by a factor of eight and makes faster algorithms possible, as eight times more one-bit values may be fit in a single CPU register (and thus manipulated at once) than one-byte values. However, packed Boolean arrays have a drawback: while optimized algorithms on bit Booleans are usually faster than those on byte Booleans, packed Boolean algorithms are often considerably harder to implement, and unoptimized algorithms using bit Booleans tend to be slower. This is because bits in memory cannot be addressed directly on a modern computing architecture. To read or write a single bit at an arbitrary offset, the byte containing it must be read and then the appropriate bit picked out. | ||