Boolean Data Type in freebasic

General discussion for topics related to the FreeBASIC project or its community.
Post Reply
MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: Boolean Data Type in freebasic

Post by MichaelW »

marcov wrote:
MichaelW wrote: Considering only code efficiency, using a byte as a logic element in 32/64-bit code makes little sense.
I don't know that any more for current CPUs. The old rule (till core2) was that Intel favoured simple, aligned code, and AMD tightly packed everything. Is a movzbl really slower than a plain mov nowadays?
Testing only MOVSX and MOV with 1, 4, and 8-byte memory operands and running a 64-bit app compiled with Version 1.02.0 (03-23-2015) under Windows 8.1 on my 2-year old laptop, which is the most recent system I have, I cannot get meaningful cycle counts for any small number of instructions. The results for a larger number of instructions are not representative of the way a boolean would typically be used, but it's the best I can do ATM. After the initial pass, for a larger number of instructions there is no significant difference between the operand sizes. Below is my test code, and counter64.bas is available here.

Code: Select all

#include "windows.bi"
#include "counter64.bas"

dim shared as byte i1
dim shared as long i4
dim shared as integer i8

'' Restrict process to a single core.

SetProcessAffinityMask( GetCurrentProcess(), 1)

sleep 5000

for i as integer = 1 to 3
    counter_begin(1000000,REALTIME_PRIORITY_CLASS,THREAD_PRIORITY_TIME_CRITICAL)
        asm
            ".intel_syntax noprefix"
            ".rept 10"
            "movsx rax, BYTE PTR I1$"
            "movsx rcx, BYTE PTR I1$"
            "movsx rdx, BYTE PTR I1$"
            ".endr"
            ".att_syntax prefix"
        end asm
    counter_end
    print counter_cycles;" cycles"    
    counter_begin(1000000,REALTIME_PRIORITY_CLASS,THREAD_PRIORITY_TIME_CRITICAL)
        asm
            ".intel_syntax noprefix"
            ".rept 10"
            "movsx rax, DWORD PTR I4$"
            "movsx rcx, DWORD PTR I4$"
            "movsx rdx, DWORD PTR I4$"
            ".endr"
            ".att_syntax prefix"
        end asm    
    counter_end
    print counter_cycles;" cycles"
    counter_begin(1000000,REALTIME_PRIORITY_CLASS,THREAD_PRIORITY_TIME_CRITICAL)
        asm
            ".intel_syntax noprefix"
            ".rept 10"
            "mov rax, QWORD PTR I8$"
            "mov rcx, QWORD PTR I8$"
            "mov rdx, QWORD PTR I8$"
            ".endr"
            ".att_syntax prefix"
        end asm    
    counter_end
    print counter_cycles;" cycles"
    print
next

sleep

Code: Select all

 71 cycles
 24 cycles
 23 cycles

 22 cycles
 22 cycles
 22 cycles

 22 cycles
 22 cycles
 22 cycles
I agree with Tourist Trap here, in that it's not reasonable to assume that most people will be running anything resembling a "current" processor.
speedfixer
Posts: 606
Joined: Nov 28, 2012 1:27
Location: CA, USA moving to WA, USA
Contact:

Re: Boolean Data Type in freebasic

Post by speedfixer »

Add boolean: makes FB more valuable with less work.


So, is there agreement on attitude of applying/optimizing BOOL?
Can a consensus be achieved?

There a many out there that have used FB for years, and many who have plans/desires to use FB for non-trivial work in the future.

Please express yourselves.


me:
Ease and flexibility of integrating external libraries is very important to FB, but internal optimization of FB as a standalone language is more important, in my opinion.

The lightening fast compiler is one great aspect of FB. But if it slows a bit to produce better code, either as FB or as gcc compiled code, then I would prefer the better code.


David
coderJeff
Site Admin
Posts: 4313
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

Re: Boolean Data Type in freebasic

Post by coderJeff »

MichealW, speedfixer, thanks for joining in!

@all, I like freebasic. I like poking around under the hood. I like sharing code I think would be useful. I hope my enthusiasm makes up for my lack of expertise. For me, this is a fun and interesting hobby. If it wasn't fun I probably would not bother. Just sayin'...

When adding boolean, some consideration was made for speed and size of code, but first: semantics. For comparison, fb's "boolean" is like C++ "bool", or java "boolean" but *not* like win api "BOOL", "BOOLEAN", or java "Boolean". By name only, all seem to be advertising the same product. They are not.

java "Boolean" is a class, like if there were a fb type (UDT) "Boolean" and that is a different animal from all the rest, so let's just leave that one out for now.

fb "boolean", c++ "bool", and java "boolean" are all buit in compiler types that come with a contract, which says "this data type shall hold either the 'false' value or the 'true' value and no other value". If the programmer tries to break that contract and assign '42' or "flurble" to a boolean it will complain as the programmer is clearly trying to break the contract.

And in fbc the 'false' and 'true' values are typed constants, not simple built-in #define's. They are declared and defined by the compiler as follows:
const FALSE as boolean = 0
const TRUE as boolean = NOT FALSE

An earlier version of fbc boolean enforced this contract ruthlessly, such that, even should a boolean come to contain something other than the false or true value (through pointer, union, file) it would force the data type to contain only false or true. This produced bloated (slow) code sequences, due to all the (usually unnecessary) checking and normalizing . So, first optimization is that we only enforce the boolean contract when a booelan variable is a assigned from some other non-boolean data type. After that, we assume the boolean variable will continue to have a false/true value only.

Also in an earlier version, fbc booleans were regularly converted to integers to allow comparison/logic operators to work as is. However, this also caused bloated code since booleans were regularly being converted to integers, operated on, then converted back to boolean for storage. So, second optimization is that boolean-only expressions returning a boolean, do not convert to integers; They stay as the boolean type. So where we have c = (a and b), where a,b,c are all booleans, can produce x86 code that is 3 instructions: mov al, [A]; and al, , mov [C], al.

Now for win api BOOL and BOOLEAN, these sound a lot like what we want, but if we read the fine print, they follow a different contract. Their contract is more like ".. shall hold either the FALSE value or TRUE value, but other values are OK too, depending on my size, it's really up to you to make sure I behave." For example in VC, only one of these statements produces a conversion warning:

bool b1 = 2; // << it's this one
BOOL b2 = 2; // int, OK
BOOLEAN b3 = 2; // unsigned char, OK

Only one statement causes a complaint because only one of these statements is breaking its contract. int's and char's can hold lots of other values besides just false and true. The WIN API's idea of a "boolean" type is really only what can be supported in C. An integer type that *should* only have false true values but could hold some other value without so much as a peep out of the compiler. Many other C libraries follow this pattern where "boolean" is really just an alias for an integer/enum/#define.

About the boolean size: 1-bit booleans are supported if you want a smaller memory footprint but don't mind the longer code sequences to access bits. Difference is that if converting bits to larger integer sizes, integers will become 0 or 1 and booleans become 0 or -1.

Code: Select all

type T
	as integer i0:1
	as boolean b1:1
	as integer i2:1
	as boolean b3:1
end type
Otherwise, for now, I have only been looking at the 1-byte sized boolean that is going to get us working with the C++/g++/bool data type in g++ libraries. It's that simple. As mentioned, not impossible to have various sizes of boolean's but we need to take first steps to get there.
MrSwiss
Posts: 3910
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Boolean Data Type in freebasic

Post by MrSwiss »

Hi all,

I've just uploaded my latest project, which makes use of Long's 'misused' as BOOLEANS. See:
http://freebasic.net/forum/viewtopic.php?f=8&t=23791

It would definitely be simpler to read if there was a BOOLEAN Type present ...

Instead of:

Code: Select all

bi(n) = 1
just as:

Code: Select all

bi(n) = TRUE
Tourist Trap
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: Boolean Data Type in freebasic

Post by Tourist Trap »

coderJeff wrote:When adding boolean, some consideration was made for speed and size of code, but first: semantics. For comparison, fb's "boolean" is like C++ "bool", or java "boolean" but *not* like win api "BOOL", "BOOLEAN", or java "Boolean". By name only, all seem to be advertising the same product. They are not.
Very nice overview. A nice introduction to the subject.
coderJeff wrote:

Code: Select all

type T
	as integer i0:1
	'(...)
end type
Could you tell me what this syntax does : as integer i0:1 ?

Other question, are you sure that it is at all useful to code the boolean type as a 1 bit sized number? I mean by there that the operators over booleans will do as if they were 1 bit anyway, so I don't see where exactly it would be a gain. Coding them as integer would at least save a conversion when needed.
I understand however that 1 bit is the mathematical size for such a type.
integer
Posts: 408
Joined: Feb 01, 2007 16:54
Location: usa

Re: Boolean Data Type in freebasic

Post by integer »

Code: Select all

    type leon
        as byte     ia:1
        as short    ib:2
        as integer  ic:3
        as long     id:4
        as byte     ie:5
        as short    ig:6        
        as integer  ih:7        
        as long     ik:8
        as integer  il:9
    end type 
    
    dim boo as leon
    
    boo.ia = 255
    boo.ib = 255
    boo.ic = 255
    boo.id = 255
    boo.ie = 255
    boo.ig = 255
    boo.ih = 255
    boo.ik = 1023
    boo.il = 1023

    print "----------"
    print boo.ia
    print boo.ib
    print boo.ic
    print boo.id
    print boo.ie
    print boo.ig
    print boo.ih
    print boo.ik
    print boo.il
    print "------------"
output:

Code: Select all

1
3
7
15
31
63
127
255
511
I have not worked with bit fields. Thus, my ignorance.
This is great to know.
We already have bit fields with which to work.

Thank you coderJeff
coderJeff
Site Admin
Posts: 4313
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

Re: Boolean Data Type in freebasic

Post by coderJeff »

@integer, that is a weird example! Good way to learn though, just try it out. bit fields are listed in the syntax of TYPE, but not in the the description:

fieldname : bits As DataType [= initializer]
As DataType fieldname : bits [= initializer], ...

however, there is a nice introductory description of "bit field" in this tuorial. -- scroll way down.

@Tourist Trap, Why not just code with integers instead of boolean? or bit fields? I don't understand what you are asking. 1-bit boolean is different from 1-bit integer.

Let's suppose we have 4 consecutive bytes in memory, with the decimal values 72, 73, 33, 0. What is it?
Is it an array of 4 bytes with those exact values?
Is it the 32-bit integer value 2181448? (little-endian)
Is it single value of 3.05686e-039?
Is it a zero terminated string with value of "HI!"?
Answer is: it is whatever we tell the compiler it should be. And different binary code gets generated depending on what type the data is. (because end result is that all data is sequence of 0's and 1's).
Tourist Trap
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: Boolean Data Type in freebasic

Post by Tourist Trap »

coderJeff wrote:Let's suppose we have 4 consecutive bytes in memory, with the decimal values 72, 73, 33, 0. What is it?
What I was thinking about is that in your implementation you would have saved the boolean value at the first bit, inside a memory unit (4 octets for 32 bits, 8 for 64 and so on), leaving so 31 bits unused. This, because I'm convinced, and I don't remember why, that it is more efficient (not for memory space however). So to say in general, in the case of any numeric types, anything smaller that an integer, can be coded inside an integer. So my remark (silly I guess).

A boolean in this affair would be written xxxx xxxx xxxx xxx1, then my final remark was just to say : 'let's fill the free space with 0', so this is again also an integer and less work for compiler... But we are going back to start with this reasonning. Sorry, and please continue posting answers in an extensive style.

Last addition, just for making all this definitely clear and to show that this is not about exactly the same implementation as today - or is it? In the kind of management pointed out above, the boolean would be an integer but that the compiler would treat as a single bit with the help of overloaded operators. For instance, 1+1 would prevented to give 10 (=2), since + for booleans would treat everything as if it was a boolean operator with as a significant result the first single bit.
coderJeff
Site Admin
Posts: 4313
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

Re: Boolean Data Type in freebasic

Post by coderJeff »

There are members here that are *way* smarter than me when it comes to microarchitecture/processors, so if any want to add something, go for it. Thanks.

dkl, has merged the boolean branch in with master on fbc's git repo, so if you can get your hands on a daily build, you will be able to try this feature out.

@MichaelW, I was thinking about "typical" use for booleans. I would guess the most likely uses of boolean would be (in order):
1) function return or variable read, for
2) comparison, then
2) conditional branch.
3) pass as parameter
4) store in variable/field

@Tourist Trap, Yep, some processors will work faster with data of certain bit-widths so read/write of 32/64-bit is going to be faster than read/write 8-bit. And alignment in memory also affects speed of read/write. There are some microarchtectures that can address single bits and have instructions to operate on single bits; some PLC's for example. But usually this single bit addressing is reserved for I/O address space only which may only be like 16 words (256 bits total) for the whole micro.

For 'xxx...xxx1' where first bits are "unused" is a problem for most architectures since there are no instructions (or at least the kind of instructions we need) to operate on single bit. Maybe processor is OK with 8 bits, or maybe we need to work with machine-word size of 16, 32, 64 bits for fastest code. At some time, we still need to do *something* with the unused bits. We can set all the "unused" bits to 0 on write and assume that they are still 0 later, or we can igore those bits, and instead mask out those bits later on when reading. Either way, extra steps are needed to operate on a single bit.

For "1+1" (in the context of boolean) we are actually meaning "TRUE+TRUE". Does that make any sense? Probably not. And if we need overloaded operators to get the desired behaviour, then we are dealing with something that is not exactly like an integer. fbc allows "TRUE" to be converted to "-1" because many other conversions in fbc are allowed so "TRUE+TRUE" gives us -2. We could produce compiler error on it instead and just not allow it.
MrSwiss
Posts: 3910
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Boolean Data Type in freebasic

Post by MrSwiss »

coderJeff wrote:For "1+1" (in the context of boolean) we are actually meaning "TRUE+TRUE". Does that make any sense? Probably not. And if we need overloaded operators to get the desired behaviour, then we are dealing with something that is not exactly like an integer. fbc allows "TRUE" to be converted to "-1" because many other conversions in fbc are allowed so "TRUE+TRUE" gives us -2. We could produce compiler error on it instead and just not allow it.
I'm not certain to understand properly.
In a strictly BOOL Type a comparison like:
If a(=TRUE) AND b(=TRUE) Then c=TRUE (or FALSE) ...
but not something like -2?
coderJeff
Site Admin
Posts: 4313
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

Re: Boolean Data Type in freebasic

Post by coderJeff »

MrSwiss, yes, it is confusing. Tourist Trap is trying to make a connection between integers and booleans. Ignore "1+1" and I will add to the other stuff..

Important to remember that booleans can have the 'true' value or the 'false' value, whereas integer types have a number value. They are two different things. fbc has no idea how to add (+) two booleans together, but it does know how to add two integers together. So, it converts the booleans to integers and then adds them together. But, if we convert a boolean to an integer, what value should the integer be?

Every version of FB before now did not have a boolean data type, and yet, the false/true concept was still needed and used. To implement this concept we can use (false=0) and (true=not false), which gives us false=0, true=-1, and logically consistent with (not true) = (false).

Therefore, "true+true" = cint(true)+cint(true) = (-1)+(-1) = -2. Does it make sense? Probably not. Should it even be allowed? Maybe not. We could produce an error and prevent user from ever writing code that tries to add two booleans together.
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Boolean Data Type in freebasic

Post by dodicat »

I think enum would be too weak to represent the C++ boolean.
Besides, the constant returned by enum is integer. (I don't think it can be changed to byte).

A full blown UDT is probably required with all the associated paraphernalia including the bits.
Anyway I spent 20 minutes or so creating some operator on enum:

Code: Select all

 
enum bool
    false=cbyte(0) 'cannot connect false as byte
    true =-(not false)' or cbyte(1)
end enum

'a few operations:
operator > (x as bool,y as bool) as bool
return -cast(bool,cast(integer,x)>cast(integer,y))
end operator

operator < (x as bool,y as bool) as bool
return -cast(bool,cast(integer,x)<cast(integer,y))
end operator

operator = (x as bool,y as bool) as bool
return -cast(bool,cast(integer,x)=cast(integer,y))
end operator

operator <> (x as bool,y as bool) as bool
return -cast(bool,cast(integer,x)<>cast(integer,y))
end operator

operator and (x as bool,y as bool) as bool
return cast(bool,cast(integer,x) and cast(integer,y))
end operator



function IsLeft(L1x as integer ,L1y as integer,L2x as integer,L2y as integer,px as integer,py as integer) as bool
  return iif(Sgn((L1x-L2x)*(py-L2y)-(px-L2x)*(L1y-L2y))<0,true,false)
end function


screen 19
dim as integer mx,my
do
    getmouse mx,my
    screenlock
    cls
line(0,30)-(800,450)
locate 4,4
print "Move the mouse across the line",
print isleft(0,30,800,450,mx,my)
#print typeof(isleft(20,30,600,450,mx,my))
screenunlock
sleep 1,1
loop until len(inkey)
cls
    dim as bool x=true,y=false
    #print typeof(x>y)
    print "x= ",x
    print "y= ",y
    print
    print "x>y", x>y
    print "x<y",x<y
    print "x=y", x=y
    y=true
    print "y is now true"
    print "x and y", y and x
    print "x=y", x=y
    #print typeof(x and y)
    print sizeof(false)
    sleep
    
MrSwiss
Posts: 3910
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Boolean Data Type in freebasic

Post by MrSwiss »

coderJeff wrote:We could produce an error and prevent user from ever writing code that tries to add two booleans together.
Yes I'd agree with you, that booleans can NOT be used as other data types can (+ - / *), only logical operators should be allowed, as well as the =[TRUE|FALSE] operator. This simply because the math's operators don't make any sense on booleans.
counting_pine
Site Admin
Posts: 6323
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: Boolean Data Type in freebasic

Post by counting_pine »

When should/shouldn't a Boolean be returned? Potentially any bitwise ops on Booleans, any intrinsic comparison operators, and the short-circuit logical ops (ANDALSO/ORELSE), could legitimately return Boolean values.
Currently it looks like bitwise and comparison operators return a Boolean when both inputs are Boolean. The short-circuit logical ops always return an Integer.

For consistency, I think ANDALSO/ORELSE should return Boolean whenever AND/OR do.

Personally, I think it would make sense if all of the above - bitwise ops on Booleans, all comparisons, and the short-circuit ops - return a Boolean value.
St_W
Posts: 1619
Joined: Feb 11, 2009 14:24
Location: Austria
Contact:

Re: Boolean Data Type in freebasic

Post by St_W »

coderJeff wrote:dkl, has merged the boolean branch in with master on fbc's git repo, so if you can get your hands on a daily build, you will be able to try this feature out.
Great. The most current builds, which were uploaded tonight, already contain these commits. You can download them at:
http://users.freebasic-portal.de/stw/builds/

I think this is the biggest change to the language since quite a long time and I hope that the new feature gets stable in reasonable time and doesn't cause too much compatibility troubles with existing programs.

When the design of the basic datatype (internal representation and such things) is considered rather stable FreeBasic users should be encouraged to try out the new feature and report encountered problems. Currently there are also some (6) failing unit tests.
Post Reply