It is currently Fri Sep 21, 2018 4:03 pm

 All times are UTC - 7 hours

 Page 2 of 2 [ 22 posts ] Go to page Previous  1, 2
 Print view Previous topic | Next topic
Author Message
 Post subject: Re: Greater than, less thanPosted: Fri May 06, 2016 7:15 pm

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1243
Yes. BEQ covers just one cmp result. It's also exclusive from BCC after a compare. So if you do beq before bcc, you're cutting out one value from a group that may not need that value cut out from it. With BCC first, you can sieve out a much larger range of values. With BEQ first, you lose two cycles on a much larger range of numbers, than if you do BCC first, where you add two cycles to just one case. (Zero.) Edit2: Well, you also add the two cycles to all the BCS cases, but if you need to perform separate logic on <, >, and = something's gotta lose, and BCS is not exclusive from BEQ after a compare. If you are doing all three, BCS is usually a better first branch.

You said in the other topic the goal is performance, and it's usually faster. (But it depends on what you're comparing. Sometimes 0 really is the most common case.)

Edited to be hopefully be better explained.

_________________
https://kasumi.itch.io/indivisible

Top

 Post subject: Re: Greater than, less thanPosted: Fri May 06, 2016 8:51 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6812
The difference is about time, not functionality. If you don't care how long it takes, then it doesn't matter.

If you do care, you'll want to arrange your code so that the most common case takes the shortest/fastest branch.

(Edit: missed Kasumi's post so this is redundant.)

Top

 Post subject: Re: Greater than, less thanPosted: Sat May 07, 2016 7:00 am

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10814
Location: Rio de Janeiro - Brazil
One obvious optimization is to start the comparison from the most significant digit and move your way down, because that will allow you to find the result without having to look at all the digits. You keep comparing while the digits in both numbers are the same, but as soon as you find one that's different, you'll have your answer. For example, when comparing 1350 and 1510, comparing 1 and 1 will not give you an answer, but comparing 3 and 5 will, so there's no need to compare the test.

With this in mind, it may be a good idea to have a BNE after each comparison branch away to a location that will use BCC/BCS to tell which number is larger (regardless of the position of the digit). Like this:

Code:
lda num1+n
cmp num2+n
bne decide
lda num1+n-1
cmp num2+n-1
bne decide
(...)
lda num1+0
cmp num2+0
bne decide
;num1 = num2
decide:
bcs greater than
;num1 < num2
greaterthan:
;num1 > num2

The loop is unrolled for speed, so you don't have to update X or check for end conditions with such small arrays (surely you don't have not than 8 digits to compare?).

Top

 Post subject: Re: Greater than, less thanPosted: Sat May 07, 2016 7:29 am

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1684
tokumaru wrote:
One obvious optimization is to start the comparison from the most significant digit and move your way down, because that will allow you to find the result without having to look at all the digits.

Yes, I know. That's why I said: The array aspect doesn't really have much to do with my question, only the question about a single comparison.

That's the way I did it now:

Code:
LeftEqualsRight = 0
LeftLessThanRight = 1
LeftGreaterThanRight = 2

.segment "ZEROPAGE"

_CompareArraysPointerLeft: .res 2
.exportzp _CompareArraysPointerLeft
_CompareArraysPointerRight: .res 2
.exportzp _CompareArraysPointerRight
Size: .res 1

.segment "CODE"

_CompareArrays:
.export _CompareArrays_

STA Size

LDY #0

@loop:

LDA (_CompareArraysPointerLeft), Y
CMP (_CompareArraysPointerRight), Y
BCC @leftLessThanRight
BEQ @leftEqualsRight

LDA #LeftGreaterThanRight
JMP @end

@leftLessThanRight:

LDA #LeftLessThanRight
JMP @end

@leftEqualsRight:

INY
CPY Size
BNE @loop
LDA #LeftEqualsRight

@end:

LDX #0

RTS

The pointers are set in the code in C before calling the function.

By the way, is there any way to do this without the Size variable?

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg

Top

 Post subject: Re: Greater than, less thanPosted: Sat May 07, 2016 7:38 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20562
Location: NE Indiana, USA (NTSC)
If you're comparing two multi-byte numbers but not doing a 3-way comparison, if you're fine with just knowing whether a < b or b >= a, you can just do most of the subtraction and ignore the result except for the carry. This method doesn't waste bytes on intermediate branches or cycles on untaken branches.
Code:
lda b_lo
cmp a_lo  ; Use CMP instead of SBC to avoid needing to SEC
lda b_mid
sbc a_mid  ; Use SBC instead of CMP to respect previous carry
lda b_hi
sbc a_hi
bcc a_is_less
; here: A is greater or equal

Top

 Post subject: Re: Greater than, less thanPosted: Sat May 07, 2016 7:49 am

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1684
tepples wrote:
If you're comparing two multi-byte numbers but not doing a 3-way comparison

It's a general purpose function. Sometimes I need to check for equal, sometimes for less than, sometimes for greater than. So, the function needs to be able to handle each case.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg

Top

 Post subject: Re: Greater than, less thanPosted: Sat May 07, 2016 11:57 am

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10814
Location: Rio de Janeiro - Brazil
I though you were shooting for speed? Your loop looks significantly slower than than the unrolled loop I posted... If you need to compare numbers of different sizes, you can just have multiple entry points (load Y with Size - 1 and JSR to the appropriate entry point):

Code:
Compare5Digits:
lda (_CompareArraysPointerLeft), y
cmp (_CompareArraysPointerRight), y
bne Decide
dey
Compare4Digits:
lda (_CompareArraysPointerLeft), y
cmp (_CompareArraysPointerRight), y
bne Decide
dey
Compare3Digits:
lda (_CompareArraysPointerLeft), y
cmp (_CompareArraysPointerRight), y
bne Decide
dey
Compare2Digits:
lda (_CompareArraysPointerLeft), y
cmp (_CompareArraysPointerRight), y
bne Decide
dey
Compare1Digit:
lda (_CompareArraysPointerLeft), y
cmp (_CompareArraysPointerRight), y
bne Decide
lda #LeftEqualsRight
rts
Decide:
bcc +
lda #LeftGreaterThanRight
rts
+ lda #LeftLessThanRight
rts

I know that coming from a high-level language your first instinct is to use a loop, handle different sizes using a parameter and a variable, and have only one return point, but now you have the power of assembly! If you really are going for speed, you should consider these kinds of optimizations.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 2 of 2 [ 22 posts ] Go to page Previous  1, 2

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: Google [Bot], Memblers and 3 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki