SWAP keyword

Forum for discussion about the documentation project.
speedfixer
Posts: 389
Joined: Nov 28, 2012 1:27
Location: California

SWAP keyword

Postby speedfixer » May 04, 2019 5:20

Could you add a note - doesn't have to be exactly this.

While SWAP is simple to use, it is typically faster for all but integer types. A proxy-type swap is usually faster for integer types. As always, if speed is critical, test the alternatives IN YOUR PROGRAM.


My test code:

Code: Select all

type udt
    ii as integer
    ss as string
end type

dim as udt uu1, uu2, uuproxy
dim as string sa, sb, sproxy

dim as integer ia, ib, iproxy
dim as integer count

'count = 10000
count = 1000000
'count = 100000000

dim as double xxtime, stime1, stime2, stime3
dim as double ptime1, ptime2, ptime3

sa = "test"
sb = "text"

ia = 44
ib = -124

uu1.ii = ia
uu1.ss = sa

uu2.ss = sb
uu2.ii = ib

xxtime = timer
for y as integer = 1 to count
    swap ia, ib
next
stime1 = timer - xxtime

sleep 5,1

xxtime = timer
for y as integer = 1 to count
    swap sa, sb
next
stime2 = timer - xxtime

sleep 5,1

xxtime = timer
for y as integer = 1 to count
    swap uu1, uu2
next
stime3 = timer - xxtime

sleep 5,1

xxtime = timer
for y as integer = 1 to count
    iproxy = ia
    ia = ib
    ib = iproxy
next
ptime1 = timer - xxtime

sleep 5,1

xxtime = timer
for y as integer = 1 to count
    sproxy = sa
    sa = sb
    sb = sproxy
next
ptime2 = timer - xxtime

sleep 5,1

xxtime = timer
for y as integer = 1 to count
    uuproxy = uu1
    uu1 = uu2
    uu2 = uuproxy
next
ptime3 = timer - xxtime


print tab(9); "swap time"; tab(38); "proxy time"
print
print " int: "; stime1; tab(36); ptime1
print " str: "; stime2; tab(36); ptime2
print " udt: "; stime3; tab(36); ptime3
print
print "integer swap/proxy ratio: "; stime1/ptime1
print


On my system, typical times:

david@deb9:~/Desktop$ ./test
-------- swap time------------------------------ proxy time

int -- 0.008764028549194336 ------------ 0.003302097320556641
str -- 0.007848978042602539 ------------ 0.04162502288818359
udt -- 0.009058952331542969 ------------ 0.05147504806518555

integer swap/proxy ratio: 2.654079422382671

string proxy/swap ratio: 5.303241092311898

udt proxy/swap ratio: 5.682229708390357


Results shown are for program provided.
With this code, it varies between 2.5+ up to 3 times slower on my usual test/coding system.

A LARGE caveat: For the integers SWAP is very code touchy.
With other code and on other machines, I have seen it as much as 6 times slower.

BUT ---
For my PI3B+ (4 core) and this same system (Debian w/6 core AMD) - the higher and the lower counts in the code above BOTH gave an integer .9 ratio !!
I would be interested to hear what differences others see, or if someone could even suggest why integer SWAP is so touchy.


Thanks
david
fxm
Posts: 9256
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: SWAP keyword

Postby fxm » May 04, 2019 6:23

With my PC, I get these results on average (Intel Core i7):

Code: Select all

        swap time                    proxy time

 int:  0.002591400000039323         0.002317400000180658
 str:  0.005428399999780398         0.07824619999981763
 udt:  0.006148499999863333         0.1149699999999512

integer swap/proxy ratio:  1.11823595401627

The results are about equivalent for integers.

The Swap statement is faster for var-len strings and UDTs that contain var-len strings:
- because for var-len strings, the string data characters are not swapped themselves but only the string descriptors (always only 3 integers to swap).
I will add this in the documentation via a note.

If we exchange the order of tests (at first the proxys, then the swaps), the trend for integers is reversed.
jj2007
Posts: 1259
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: SWAP keyword

Postby jj2007 » May 04, 2019 8:20

Intel Core i5, not the latest model, GAS:

Code: Select all

        swap time                    proxy time

 int:  0.003103105379864246         0.003105157893855903
 str:  0.007858134918478754         0.08723219351736589
 udt:  0.009785106172330416         0.1015518810260119

integer swap/proxy ratio:  0.9993389985109232

Under the hood, there is little to improve:

Code: Select all

  push dword ptr [ebp-5C]
  mov eax, [ebp-60]
  mov [ebp-5C], eax
  pop dword ptr [ebp-60]

And just in case you have a desperate need for speed, with this you get a 0.75 ratio:

Code: Select all

for y as integer = 1 to count
#if 1
  asm mov edx, [ebp-&h5C]
  asm mov eax, [ebp-&h60]
  asm mov [ebp-&h5C], eax
  asm mov [ebp-&h60], edx
#else
    swap ia, ib
#endif
next

P.S.: With gcc, it's a little bit faster: int: -6.26e-011 (the compiler is clever, hehe...).
MrSwiss
Posts: 3305
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: SWAP keyword

Postby MrSwiss » May 04, 2019 8:54

C:\DEV_TOOLS\FreeBASIC\1060_64\fbc -s console "xyz.bas" (no optimisations)
Intel i7 7th gen. (U model), dual core (4 virtual), WIN10 pro 64

Code: Select all

        swap time                    proxy time

 int:  0.002437999937683344         0.002927400171756744
 str:  0.006706200074404478         0.05453830002807081
 udt:  0.01079980004578829          0.04852829989977181

integer swap/proxy ratio:  0.8328208631006162
proxy always slower than swap ...
fxm
Posts: 9256
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: SWAP keyword

Postby fxm » May 04, 2019 9:12

Documentation updated:
KeyPgSwap → fxm [Added a note that what Swap is optimized for var-len strings]
MrSwiss
Posts: 3305
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: SWAP keyword

Postby MrSwiss » May 04, 2019 11:20

fxm wrote:KeyPgSwap → fxm [Added a note that what Swap is optimized for var-len strings]
This is not exactly the whole truth, because it applies likewise, to PTR's in UDT's
(any data-type or UDT), where the allocated memory is always external to the
UDT itself (only the PTR's size is allocated, inside the UDT).

A var-len string is nothing but a FB-Type, containing:
    zstring ptr (string data)
    integer (string len)
    integer (allocated memory size)
fxm
Posts: 9256
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: SWAP keyword

Postby fxm » May 04, 2019 12:13

The optimization of Swap is evaluated compared to the reference of 3 assignments.

For var-len strings s1 and s2,
Swap s1, s2
is optimized compared to
s0 = s1
s1 = s2
s2 = s0


For objects u1 and u2 of UDT containing a pointer,
Swap u1, u2
is not optimized compared to
u0 = u1
u1 = u2
u2 = u0

because both are doing the same thing (raw copy of UDT field).
MrSwiss
Posts: 3305
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: SWAP keyword

Postby MrSwiss » May 04, 2019 13:04

Sorry, doesn't make the tiniest bit of sense, by cons, it's just illogical,
at least as long, as you can't describe the very details of optimizing,
that is "supposedly" taking place ...

A Ptr in a UDT "u" and, a Ptr in the UDT "String", is "the same difference".
(give or take the two integer's)
fxm
Posts: 9256
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: SWAP keyword

Postby fxm » May 04, 2019 13:14

The difference is that a string is an object with a Let operator Let that copies the string data characters when assignment is called, which is not the case of an UDT containing a pointer to data block.

What do the other members think about that?
MrSwiss
Posts: 3305
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: SWAP keyword

Postby MrSwiss » May 04, 2019 13:23

fxm wrote:The difference is that a string is an object with a Let operator Let that copies the string data characters when assignment is called, which is not the case of an UDT containing a pointer to data block.
Sorry, but this is nonsense because, the DATA isn't touched at all, just the Ptr's
adresses need swapping (plus the two integer's values), aka: shallow copy.

Remember: the DATA is external, to the Type! (just pointed to)

fxm wrote:What do the other members think about that?

Let me let you in, on a little secret:
I' m currently testing a similar scenario, I'm just going to give you the Type definition,
for thinking about it (I've done so, put it in code and, testing it now) ... here goes:

Code: Select all

' ----- Type zstr_t -----
Enum zstr_state                         ' the available states of type (below)
    raw = 0                             ' - not yet init (no memory allocated)
    ini                                 ' - valid entry (aka: initialized) also: undel. use
    del                                 ' - marked deleted (still valid, until overwritten)
End Enum                                ' this is, to avoid a lot of resizing of memory

'Type poc                                ' poc = the very same size as zstr_t in FBC64
'    As String   strg                    ' in FBC32 it is 12 vs. zst_t's 20
'End Type                                ' except, for testing (backward compatibility)
'Print SizeOf(poc)                       ' if you uncomment this section, you'll see

' types size in bytes is: 24 FBC64 / 20 FBC32 (for use instead of, array of string)
' a sort of: fixed size string instance, with state and actual string length
Type zstr_t                             ' variable length fixed string type
  Private:                          ' encapsulate our 'crown jewels' <lol>
    As ZString Ptr  psz  = 0            ' menory allocated is external to type
    As ULong        stat = raw          ' see enum above (aka: 0 / zero / null)
    As ULong        slen = 0            ' stored strings effective length
    As ULong        smem = 0            ' stored effective memory size allocated
    As ULong        res  = 0            ' reserved (future use)
    ' string memory is always slen + 1, dynamically callocated (outside type)
  Public:                           ' public interface (limited access!):
    Declare Destructor                      ' - just calls free (custom destructor)
    Declare Sub snew(ByVal As ZString Ptr)  ' - init string or store new string
    Declare Sub set_stat(ByVal As ULong)    ' - set new status (raw is NOT allowed!)
    Declare Function sget() As String       ' - get string (dereferenced zstring ptr)
    Declare Function get_stat() As String   ' - verbose status (as in enum)
    Declare Function get_slen() As String   ' - string-length for print (string)
    Declare Function get_smem() As String   ' - mem. alloc'ed for print (string)   
    Declare Function get_nlen() As ULong    ' - string-length as number (ULong)
    Declare Function get_nmem() As ULong    ' - mem. alloc'ed as number (ULong)
    Declare Sub free()                      ' - deallocate string memory (cust. dtor)
    Declare Operator Let(ByVal As ZString Ptr)  ' - enables straight assignment '=' _
End Type                                    ' for those, incapable of, using a Sub :-((
It even has a Let-Operator but, with a sarcastic comment.
It's simply calling the Sub, which some users seem not to be capable, of using.
If it's good for anything then, for furthering lazyness ... otherwise, just one more
"layer of obfuscation".
Last edited by MrSwiss on May 04, 2019 14:11, edited 1 time in total.
fxm
Posts: 9256
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: SWAP keyword

Postby fxm » May 04, 2019 13:37

MrSwiss wrote:

Code: Select all

        swap time                    proxy time

 str:  0.006706200074404478         0.05453830002807081
So you see no improvement between the left column and the right column?
MrSwiss
Posts: 3305
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: SWAP keyword

Postby MrSwiss » May 04, 2019 14:18

fxm wrote:
MrSwiss wrote:

Code: Select all

        swap time                    proxy time

 str:  0.006706200074404478         0.05453830002807081
So you see no improvement between the left column and the right column?
Absolutely pointless question because:
    compare: apples with apples
to do that, the current testing code is useless.

What does useless test code proof? (rhetoric question)
Answer: abslutely nothing! (correct answer)
fxm
Posts: 9256
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: SWAP keyword

Postby fxm » May 04, 2019 14:22

I think that misunderstanding on this subject is definitive between us.
Tourist Trap
Posts: 2768
Joined: Jun 02, 2015 16:24

Re: SWAP keyword

Postby Tourist Trap » May 04, 2019 14:23

speedfixer wrote:I would be interested to hear what differences others see, or if someone could even suggest why integer SWAP is so touchy.

Hi speedfixer,

here my results on
Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz, 1992 MHz, 4 cœur(s), 8 processeur(s) logique(s)

swap time proxy time

int: 0.003723900013142156 .............. 0.004064999906518096
str: 0.009792499973741542 .............. 0.1127549999412167
udt: 0.03668219991789101.............. 0.1882844998986002

integer swap/proxy ratio: 0.9160885851856977

Seems that swap is slightly better than nothing with integers. However quite efficent in the other cases, with a few degrees of magnitude.
MrSwiss
Posts: 3305
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: SWAP keyword

Postby MrSwiss » May 04, 2019 14:46

fxm wrote:I think that misunderstanding on this subject is definitive between us.

OK, i'll try, one more time:
the left / right columns of results proof nothing, because:

the comparison should be: String vs. Type (identical to String) both with Swap,
which I expect to result in: equality (more or less) you're expecting: String, to be far faster
because of your (behind the scenes, dunno) optimisations.

Why? Because you stated that String is optimized vs. Type (which is a no.no.).

Return to “Documentation”

Who is online

Users browsing this forum: No registered users and 0 guests