Long Logical Expressions in If Statements 에서 최적화 문제 - 제 생각이 맞는거 아닌가요

kicom95의 이미지

http://www.devx.com/amd/Article/21314

를 보면

#5. Leverage the early termination abilities of complex If statements

As seen above, as soon as a true operand is found in an OR expression, or a false one is found in an AND expression, execution of that particular expression is terminated because outcome is known. You can leverage that, if you have a good idea as to whether an entire expression is likely to be true or false, to try to short-cut execution of the condition.

For example, say you're testing to see if a and b are going to be within a specified numeric range. If you know that those numbers will generally be within that range, you can use the following because the most likely outcome will evaluate to false and thereby terminate the AND condition:

if (a <= max && a >= min && b <= max && b >= min)

If you know that the data will generally not be in a specified range, you can logically reverse the If statement to optimize execution in the same way, with a true terminating the OR condition:
if (a > max || a < min || b > max || b < min)

이렇게 되어 있습니다

여기에서 설명하고자 하는 말은 논리적 연산이 && 로만 나오거나 || 로 나올떄...

&& 나 || 은 short circuit 를 지원하므로

&& 의 경우 첫번쨰 조건이 가장 false 가 많이 날 만한 조건을 앞에 내세우고

|| 의 경우 첫번쨰 조건이 가장 true 가 많이 날 만한 조건을 앞에 내세우면

뒷 부분의 조건은 검사를 하지 않아도 결과가 나온다는 의미입니다.

if (a > max || a < min || b > max || b < min) 

의 코딩은 이게 맞다고 생각되는데... 대부분의 수가 구간 밖에 있는 경우니까...

if (a <= max && a >= min && b <= max && b >= min)

은 설명 자체가 이해가 안됩니다.

a ,b 가 구간 [min,max] 에 있는지 확인을 하는 코드인데 ( 코드 자체는 확인하는 코드입니다 )

the most likely outcome will evaluate to false and thereby terminate the AND condition

를 보면 대부분의 수가 false 가 된다고 나오는데... 잘 이해가 안됩니다...

대부분의 수가 구간 안에 있으니까 true 를 리턴하는거 아닌가요 ㅠ.ㅠ

공신력있는 페이지의 글이라서 오타라면 바로 수정이 되었을 텐데....

영어 문장과 코드가 맞지 않는듯 합니다... amd cpu 상에서 저렇게 쓰는게 최적화 된다는 건지..

갑자기 프로그래밍 처음 배우는 사람이 된듯한 기분입니다....

저좀 이해좀 시켜주세요 ㅠ.ㅠ 제가 어디에서 이해를 잘못 하고 있는거 같아요 ㅠ.ㅠ

제 생각에는 위의 설명을 맞추기 위해서는

if (a > max && a < min && b > max && b < min)

의 코딩은 이게 맞다고 생각되는데... 대부분의 수가 구간 밖에 있다면....

거의 첫번쨰 && 문에서 false 를 리턴하니까요.

좀더 첨부하자면

http://cdrom.amd.com/21860/updates/Backup_Optimization_guide/wwhelp/wwhimpl/common/html/wwhelp.htm?context=OptguideHelp&file=OptguideHelp-06-06.html

를 보면

Preferred for Data that Falls Mostly Within the Range

if (a <= max && a >= min && b <= max && b >= min)

If most of the data falls within the range, the branches will not be taken, so the above code is preferred. Otherwise, the following code is preferred.

Preferred for Data that Does Not Fall Mostly Within the Range

if (a <= max && a >= min && b <= max && b >= min)

라고 되어 있는디.. 첫 부분은 또 이해가 안갑니다. ;;

mithrandir의 이미지

5번은 경우로 든 케이스 자체가 잘못됐군요.

&&든, ||든, a가 범위를 벗어난 수를 검사한다면 뒤쪽 검사를 안하고 넘어갈테고, 안쪽이라면 전부 맞는지 검사를 해야합니다.

그리고 a,b 의 경우를 생각해봐도 마찬가지로, &&를 쓰든 ||를 쓰든 a와 b가 모두 범위 안쪽에 있는지를 판단하기 때문에 a가 범위 안쪽이라면 반드시 b를 검사해야 합니다.

수정예로 드신

if (a > max && a < min && b > max && b < min)

는 항상 거짓입니다. max보다 크면서 동시에 min보다 작을수는 없겠죠?

그런데 amd페이지에서도 같은글이 있는걸 보고 아무래도 의심스러워서 컴파일을 해봤습니다.

int x(int a,int b, int max, int min)
{
        int c=-1;
        printf("%d\n", c);
        if (a <= max && a >= min && b <= max && b >= min)
        {
                c=1;
        }
        else
        {
                c=0;
        }
        return c;
}

이게 1번,
int x(int a,int b, int max, int min)
{
        int c=-1;
        printf("%d\n", c);
        if (!(a > max || a < min || b > max || b < min))
        {
                c=1;
        }
        else
        {
                c=0;
        }
        return c;
}

이게 2번입니다.

컴파일 옵션은 gcc -O0 -g -c 를 사용했습니다.

objdump test.o -d -S
로 결과를 확인해봤습니다.
결과는 두가지 모두 동일하게 나타납니다. if문 부분만 발취해봤습니다.

  20:   8b 45 08                mov    0x8(%ebp),%eax
  23:   3b 45 10                cmp    0x10(%ebp),%eax
  26:   7f 21                   jg     49 <x+0x49>
  28:   8b 45 08                mov    0x8(%ebp),%eax
  2b:   3b 45 14                cmp    0x14(%ebp),%eax
  2e:   7c 19                   jl     49 <x+0x49>
  30:   8b 45 0c                mov    0xc(%ebp),%eax
  33:   3b 45 10                cmp    0x10(%ebp),%eax
  36:   7f 11                   jg     49 <x+0x49>
  38:   8b 45 0c                mov    0xc(%ebp),%eax
  3b:   3b 45 14                cmp    0x14(%ebp),%eax
  3e:   7c 09                   jl     49 <x+0x49>

두번째 링크에서 링크된 density of branch는 branch prediction의 제약사항 때문에 분기문이 여러개 붙어있을때 prediction이 잘 안될 수도 있다는 뜻 같은데, 지식이 얕아서 잘 모르겠군요.

아무튼 short curcuit이라면 잘못된 예를 든것이 맞습니다.
----
언제나 삽질 - http://tisphie.net/typo/

언제나 삽질 - http://tisphie.net/typo/
프로그래밍 언어 개발 - http://langdev.net

kicom95의 이미지

이거 이해 해볼라고 하루 날렸지요...

하여튼 개념만 생각하고 예제는 잊을래요... ㅠ.ㅠ

어셈블리까지 보여 주시고 정말 감사합니다.

가자 해외로 ~ .. 돈 벌러.

가자 해외로 ~ .. 돈 벌러.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.