Rect_t - optimized type definition

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
MrSwiss
Posts: 3910
Joined: Jun 02, 2013 9:27
Location: Switzerland

Rect_t - optimized type definition

Post by MrSwiss »

This is NOT for those thinking: "we have the memory, let's use it" (because, I don't agree, with that opinion).

All others, might want to read on. First a small Q & A, about optimizing a
common rectangle type (called: Rect_t):

Code: Select all

' a commonly seen rectangle-type: a truly memory wasting beast (as soon as arrays are used)
Type Rect_t                     ' NOTE: alignment means, without 'field = 1' statement
    As Integer  _x, _y, _w, _h  ' FBC32 = 20 Bytes | FBC64 = 36 Bytes (alignment = 40)
    As ULong    _c              ' Question: can't we do any better?
End Type                        ' Answer: yes, we can optimize quite a lot

' first step: get rid of 'Integer' (use fixed size int-types)
Type Rect_t                     ' see below
    As Long     _x, _y, _w, _h  ' FBC32 = 20 Bytes | FBC64 = 20 Bytes | equal size
    As ULong    _c              ' Question: is this all really needed?
End Type                        ' Answer: not really, there are non essential parts

' second step: remove what is not essential
Type Rect_t                     ' FBC32 = 8 Bytes | FBC64 = 8 Bytes | equal size
    As Long     _w, _h          ' Question: do we really need a 32 bit int-type?
End Type                        ' Answer: not really, a 16 bit int type is large enough

' third step: reduce type size (to a level conformant to current/tomorrows screen sizes)
Type Rect_t                     ' FBC32 = 4 Bytes | FBC64 = 4 Bytes | equal size
    As Short    _w, _h          ' Question: do we have a option to speed up?
End Type                        ' Answer: yes, we can use the unsigned equivalent

' fourth step: use unsigned instead of signed (signed is not reqired here)
Type Rect_t                     ' FBC32 = 4 Bytes | FBC64 = 4 Bytes | equal size
    As UShort   _w, _h          ' Question: do we have all that is needed?
End Type                        ' Answer: yes, all there and mem./speed optimized
By now, you are probably thinking: "he is gone totally bonkers, now!"
But I'm willing to show, that a tiny type like above (shrunk to 4 Bytes size) is,
in fact all that is really needed, to put a simple rectangle to screen ...
For ease of use and, for re-usability I've made a .bi file (containing all type
related stuff), called:

Rect_t.bi (whole implementation):

Code: Select all

' Rect_t.bi -- 2018-08-09, MrSwiss
'
#Pragma Once                            ' only loaded once (include guard)
' ----- start type -----
Type Rect_t                             ' a very basic rectangle type (only: width/height, held internally)
  Private:                              ' no direct user access (to variables)
    As UShort   w, h                    ' variables (unsigned 16 bit integer)
  Public:                               ' interface (gives some rights, to user)
    Declare Constructor(ByVal w1 As UShort, ByVal h1 As UShort)     ' construct & assign values
    ' actor: put rectangle to screen at: x/y, with color: clr and fill: fll (default=FALSE=NOT filled)
    Declare Sub show(ByVal x As Short, ByVal y As Short, ByVal clr As ULong=&hFF7F007F, ByVal fll As Boolean=FALSE)
    Declare Sub setn(ByVal nw As UShort=0, ByVal nh As UShort=0)    ' setter: change current values
    Declare Sub getv(ByRef wt As UShort=0, ByRef ht As UShort=0)    ' getter: returns stored values
    ' no need for a Destructor (default by compiler, does 'the trick')
End Type
'
Constructor Rect_t( _                   ' user defined copy-constructor (incl. assign)
    ByVal w1    As UShort, _            ' width, mandatory
    ByVal h1    As UShort  _            ' height, mandatory
    )
    This.w = w1 - 1 : This.h = h1 - 1   ' correction for: relative sizing of RECT
End Constructor
'
Sub Rect_t.show( _                      ' actor: put rectangle to screen
    ByVal x     As Short, _             ' x position, mandatory (signed 16 bit integer)
    ByVal y     As Short, _             ' y position, mandatory (signed 16 bit integer)
    ByVal clr   As ULong=&hFF7F007F, _  ' 32 bit color (default = purple), optional 
    ByVal fll   As Boolean=FALSE _      ' default, not filled Box, optional
    )
    If fll Then                         ' if fll=TRUE then, show Box filled
        Line (x, y)-Step(This.w, This.h), clr, BF   ' Step = width/height are relative to x/y
        'Line (x, y)-(x + This.w, y + This.h), clr, BF   ' absolute positioning
    Else                                ' otherwise, show Box NOT filled (default)
        Line (x, y)-Step(This.w, This.h), clr, B
    End If
End Sub

Sub Rect_t.setn( _                      ' set new value(s), default: do nothing
    ByVal nw    As UShort=0, _          ' optional new width
    ByVal nh    As UShort=0 _           ' optional new height
    )
    If nw > 0 Then THis.w = nw - 1      ' correction for: relative sizing of RECT
    If nh > 0 Then THis.h = nh - 1
End Sub

Sub Rect_t.getv( _                      ' get currently set value(s)
    ByRef wt    As UShort=0, _          ' optional width (if var. provided)
    ByRef ht    As UShort=0 _           ' optional height (if var. provided)
    )
    wt = This.w + 1 : ht = This.h + 1   ' correction for: real size
End Sub
' ----- end type -----
Of course, I'm also adding a Test/Demo file:

Code: Select all

' simplest_RECTANGLE_type.bas -- 2018-08-10, MrSwiss
'
' compile: -s gui
'
#Include "Rect_t.bi"                    ' load the rectangle type

' macros ...
#Define RndARGB         ( CULng(Rnd * &hFFFFFFFFul) )       ' all color32 random, incl. alpha
#Define RngShrt(l, h)   ( CShort(Rnd * ((h) - (l)) + (l)) ) ' random number from a defined range

Const As UShort     scr_w = 1280, scr_h = 768, _            ' this two can be adjusted, by user
                    cd = 32, pg = 2, fg = 64                ' this stuff must remain unchanged!

' ===== start main =====
ScreenRes(scr_W, scr_h, cd, pg, fg)     ' window sizes | 32 bit color | 2 pages | using alpha
Var sp1 = 1, sp2 = 0                    ' screen pages (for buffer swapping)
ScreenSet(sp1, sp2)                     ' pre-set first buffer (to be drawn/shown)

Dim As Rect_t Ptr   prec(1 To 30)       ' array of rect_t ptr (number of rectangles)
Dim As Short        lba = LBound(prec), uba = UBound(prec)  ' store current array definitions
Dim As short        tl_offs = -(scr_h Shr 4)    ' top/left offset (based on assumed smaller size)
Dim As Boolean      flg1 = TRUE         ' process control (fill, no fill)

For i As UInteger = lba To uba          ' initialize the ptr array (copy constructor call)
    prec(i) = New Rect_t(RngShrt(scr_W * .1, scr_w * .4), _ ' min. = 10% | max. 40% (of width)
                         RngShrt(scr_h * .05, scr_h * .3))  ' min. = 5% | max. 30% (of height)
Next                                    ' use macros for sizing (fixed min/max aspect ratio's _
                                        ' but, based on current screen sizes used)
Do
    If Len(InKey()) > 0 Then Exit Do    ' on user action --> EXIT LOOP (quit prog.)
    Cls
    For i As UInteger = lba To uba      ' rectangles to screen (using macros for pos. & color)
        prec(i)->show(RngShrt(tl_offs, scr_w - tl_offs), _  ' positioning wit offset, based _
                      RngShrt(tl_offs, scr_h - tl_offs), _  ' on the current width/height used
                      RndARGB, flg1)    ' random color | fill/no fill (switches each run!)
    Next
    Draw String (30, 21), "type size: " + Str(SizeOf(*prec(lba)))   ' show types size (4 bytes)
    Swap sp1, sp2 : ScreenSet(sp1, sp2) ' swap visible/working page (show latest drawn buffer)
    flg1 = Not flg1 : Sleep(500, 1)     ' invert flag | free some CPU (let user see it 0.5 sec.)
Loop
' clean up ...
For i As UInteger = lba To uba          ' whole array (free allocated ptr's memory)
    Delete(prec(i))                     ' delete ptr's (default destructor call)
Next
' ===== end main =====  ' ----- EOF -----
Imortis
Moderator
Posts: 1923
Joined: Jun 02, 2005 15:10
Location: USA
Contact:

Re: Rect_t - optimized type definition

Post by Imortis »

I also do like the "memory is cheap" argument. This is actually an interesting way to do this task. I think this technique could be applied to lots of things. It makes the code simpler and makes the USING the code a bit clearer as it does not hide everything directly inside the object.

Thanks for sharing!
UEZ
Posts: 972
Joined: May 05, 2017 19:59
Location: Germany

Re: Rect_t - optimized type definition

Post by UEZ »

@MrSwiss: nice example with good documentation!

Thanks for sharing.

Btw, x64 seems to use less memory than x86.
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Rect_t - optimized type definition

Post by jj2007 »

SMALL_RECT has been around for a while. Using a condensed version of RECT is OK if memory is an argument (i.e. if you need to manage millions of rectangles). There is a performance penalty for accessing them, though. It is small but if you need to manage millions, it may be noticeable.
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Rect_t - optimized type definition

Post by fxm »

I would prefer two properties (getter and setter) for each dimension instead of two methods (getter and setter) for both together.
This frees the value "0" as a potentially active value.
Therefore, instead of systematically applying the "correction for: relative sizing of RECT", the real dimensions of the user rectangle (in pixels) would be stored in the attributes of the rectangle, thus allowing to define also a "null" rectangle (one dimension is equal to zero at least).
The correction ('-1') being applied only at the level of the drawing method, taking into account at least one zero dimension so as not to draw the rectangle:

Code: Select all

    If This.w > 0 Andalso This.h > 0 Then                            ' if two dimensions not null, show box
        If fll Then                                                  ' if fll=TRUE then, show Box filled
            Line (x, y)-Step(This.w - 1, This.h - 1), clr, BF        ' Step = width/height are relative to x/y
            'Line (x, y)-(x + This.w - 1, y + This.h - 1), clr, BF   ' absolute positioning
        Else                                                         ' otherwise, show Box NOT filled (default)
            Line (x, y)-Step(This.w - 1, This.h - 1), clr, B
        End If
    End If
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Rect_t - optimized type definition

Post by dodicat »

Seems unduly complicated.
udt pointers ?

You can do the same with one field variable and one function (method)

Code: Select all

#define mk(a,b) a or b shl 16
#define cr rgba(rnd*255,rnd*255,rnd*255,100+rnd*155)
Type rect
    As Long n
    Declare Function create(As Short=0,As Short=0, As Ulong=0,As Long=1) Byref As Long
End Type

Function rect.create(w As Short,h As Short,c As Ulong=0,bt As Long)Byref As Long
    If bt=1 Then Line(w,h)-(w+Loword(n),h+Hiword(n)),c,bf _
            Else Line(w,h)-(w+Loword(n),h+Hiword(n)),c,b 
    Return n
End Function


Randomize
Screen 19,32,,64
Dim As rect z
Dim As Byte b=1
Do
    b=-b
    Cls
    For n As Long=1 To 20
        z.create()=mk(Rnd*300,Rnd*300)  'get width and height
        z.create(Rnd*800-Rnd*100,Rnd*600-Rnd*100,cr,b) 'set at x,y with colour and flag for filling (or not) 
    Next n
    Sleep 500,1
Loop Until Len(Inkey)
Sleep



  
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Rect_t - optimized type definition

Post by fxm »

1 Long + Loword/Hiword is equivalent (for memory size / execution time) to 2 Shorts.
In addition, your code does not do the same as his (these are the same rectangles that are moved and recolored).
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Rect_t - optimized type definition

Post by dodicat »

If a rectangle has a different width and height, has a different colour and is drawn in a different position from another rectangle, then it is a different rectangle in my book.
An array of rectangle pointers or rectangles is hardly required for a splash demo on the screen.
But if required:

Code: Select all

#define mk(a,b) a or b shl 16
#define cr rgba(rnd*255,rnd*255,rnd*255,100+rnd*155)
Type rect
    As Long n
    Declare Function create(As Short=0,As Short=0, As Ulong=0,As Long=1) Byref As Long
End Type

Function rect.create(w As Short,h As Short,c As Ulong=0,bt As Long)Byref As Long
    If bt=1 Then Line(w,h)-(w+Loword(n),h+Hiword(n)),c,bf _
            Else Line(w,h)-(w+Loword(n),h+Hiword(n)),c,b 
    Return n
End Function


Randomize
Screen 19,32,,64
Dim As rect z(50)
for n as long=0 to 49
    z(n).create()=mk(rnd*200,rnd*200)
next
z(50).create()=mk(400,5) 'a unique long rectangle
Dim As Byte b=1
Do
    b=-b
    Cls
    For n As Long=0 To 49
        z(n).create(Rnd*800-rnd*100,Rnd*600-Rnd*100,cr,b) 'set at x,y with colour and flag for filling (or not) 
    Next n
    z(50).create(rnd*200,rnd*600,rgb(255,255,255),-b)
    Sleep 1000,1
Loop Until Len(Inkey)
Sleep
  
MrSwiss
Posts: 3910
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Rect_t - optimized type definition

Post by MrSwiss »

Imortis wrote:This is actually an interesting way to do this task. I think this technique could be applied to lots of things.
Thank you, you obviously understood, the main idea "behind the scenes" ...
UEZ wrote:Btw, x64 seems to use less memory than x86.
Thank you, too.
Have you figured out the reason yet? I'm getting about triple size memory use, in x86
compared to x64 ...
It's the needed emulator (WoW), that's apparently consuming quite a lot of memory.
fxm wrote:I would prefer two properties (getter and setter) for each dimension instead of two methods (getter and setter) for both together.
Sorry, but preferences tend to differ ... period. The remaining issues are only
of value, if one would accept your preferences, as a first step.
Btw: stuff like you are proposing (the -1's in Line statements) is exactly, what I'm
trying hard to avoid, like the plague ... show Sub's speed, is paramount.
dodicat wrote:udt pointers ?
fxm, answered already some of it (size of type = same difference).
For above, why not for a change, use some new features of FB like: New / Delete ?
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Rect_t - optimized type definition

Post by fxm »

dodicat wrote:If a rectangle has a different width and height, has a different colour and is drawn in a different position from another rectangle, then it is a different rectangle in my book.
In Euclidean plane geometry, a rectangle is a quadrilateral with four right angles.
So, it is only defined by its width and its height.
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Rect_t - optimized type definition

Post by fxm »

MrSwiss wrote:stuff like you are proposing (the -1's in Line statements) is exactly, what I'm
trying hard to avoid, like the plague ... show Sub's speed, is paramount.
Subtract -1 is negligible compared to the execution time of the Line statement.
MrSwiss
Posts: 3910
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Rect_t - optimized type definition

Post by MrSwiss »

fxm wrote:Subtract -1 is negligible compared to the execution time of the Line statement.
If we want to stay "hairsplittingly" correct, then:
you are going to subtract (a positive) 1 ...
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Rect_t - optimized type definition

Post by fxm »

:-)
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Rect_t - optimized type definition

Post by dodicat »

Mr Swiss.
If the comment was pointed at me.
features like new and delete introduce unnecessary complications.
As are pointers in general when they are not needed.

fxm
Obviously width and height are not enough to define a rectangle.
Thus a function is required to pass a position and colour.
My Euclidean plane is a rectangle on a monitor.
But even High School geometry requires a position, paper, coloured pencils.
I believe the ancient Greek mathematicians did however conjure up things like virtual shapes, and got scribes to actually draw them.
But I could be mistaken.

generally
byref methods can simulate properties, and are more versatile(Multiple parameters)
This comment is IMHO.
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Rect_t - optimized type definition

Post by fxm »

- You confuse the notion of geometrical figure with its physical representation in a given referential.

- To interface with private attributes, the property's interest is that, seen by the user, it is almost as if he were accessing the variables themselves naturally and directly.
Last edited by fxm on Aug 12, 2018 5:15, edited 1 time in total.
Post Reply