문자열처리방법에대해서....

jjjjrr의 이미지

안녕하세요
자주질문드립니다
memchr 나 memcpy strstr strcpy 등등의 문자열관련함수들의
내부동작이 어떻게되는지 알고싶은데여
라이브러리구현코드를 구할수는 없나요

궁금한부분이
memchr 에서 특정문자를 찿을경우
한바이트식읽어서 찿는것인지
아님 다른알고리즘에의해서
한꺼번에 많은양을 검사할수가있는건지...
궁금합니다
특정 텍스트처리를 할경우
저같은경우는 한바이트식읽어서 비교하고 조작하는방법을 사용하면
편하겠는데 속도에서 느릴까바
위의 함수를 사용하려구합니다
몇백메가의 파일을 읽을 경우
한바이트식읽는경우와
몇키로바이트의 버퍼를 생성하고 버퍼를 통해서한꺼번에많은양을 읽는것은
속도차이가 많이날것같은데여 어떤가여?
고수님들의 조언부탁드립니다

세벌의 이미지

차ㅊ으십니까? 차ㅈ으십니까?

익명 사용자의 이미지

그런 것은..........
어쨌거나 내부적으로는 한바이트씩 다 비교하게 되요

익명 사용자의 이미지

문자열의 경우에는 rabin-karp 알고리즘, Boyer-Moore 알고리즘, Knuth-Morris-Pratt 알고리즘과 같이 좀 더 효율적으로 검색할 수 있는 알고리즘들이 있습니다. 다만 그렇다고 해도 찾아야 될 데이터 전체를 읽어야 된다는 점에는 변함이 없고, 다만 같은 부분을 여러번 읽어야 할 필요를 줄여서 단순한(?) 방법보다 속도를 올릴 뿐입니다.

그리고 복사의 경우에는 컴퓨터 구조에 맞는 최적의 방법을 써서 속도를 최적화하기도 합니다. 예를 들면 1바이트씩 복사하는 것보다는 정렬제한에 맞게 4의 배수를 갖는 주소값부터 4바이트씩 복사하는 것이 더 빠를 것입니다. 만약 src와 dest의 시작주소가 모두 4의 배수라면(즉 정렬제한을 지키고 있다면) 4바이트씩 복사하는 것이 더 빠를 수도 있습니다.

어쨌든간에... OS 혹은 컴파일러에서 제공하는 함수들은 대부분 상당한 최적화를 거친 후에 나온 것들이므로 웬만큼 자신이 없는 한 그대로 믿고 쓰시는 것이 좋습니다.

simpid의 이미지

Anonymous wrote:
문자열의 경우에는 rabin-karp 알고리즘, Boyer-Moore 알고리즘, Knuth-Morris-Pratt 알고리즘과 같이 좀 더 효율적으로 검색할 수 있는 알고리즘들이 있습니다. 다만 그렇다고 해도 찾아야 될 데이터 전체를 읽어야 된다는 점에는 변함이 없고, 다만 같은 부분을 여러번 읽어야 할 필요를 줄여서 단순한(?) 방법보다 속도를 올릴 뿐입니다.

그리고 복사의 경우에는 컴퓨터 구조에 맞는 최적의 방법을 써서 속도를 최적화하기도 합니다. 예를 들면 1바이트씩 복사하는 것보다는 정렬제한에 맞게 4의 배수를 갖는 주소값부터 4바이트씩 복사하는 것이 더 빠를 것입니다. 만약 src와 dest의 시작주소가 모두 4의 배수라면(즉 정렬제한을 지키고 있다면) 4바이트씩 복사하는 것이 더 빠를 수도 있습니다.

어쨌든간에... OS 혹은 컴파일러에서 제공하는 함수들은 대부분 상당한 최적화를 거친 후에 나온 것들이므로 웬만큼 자신이 없는 한 그대로 믿고 쓰시는 것이 좋습니다.

텍스트 검색에 좋은 알고리즘은 많이 있지만...
x86 CPU의 경우 무식하게 rep scasb 를 사용하는게 최고로 알고있습니다.

좋은 검색 알고리즘을 구현하는 오버헤드로 좋은 알고리즘이 성능이 나오지 않습니다.

Michale Abrash의 책에서 본 내용입니다.
C로 최적화 해서 구현하고 그걸 다시 100%어셈블러로 작성해도 rep scasb 를 사용한것보다 느립니다.

허무하죠.

복사의 경우는 x86의 경우 rep movsd 등 4바이트 를 동시에 전송하는 코드를 쓰면 빠를것 같지만... 아닙니다.
루프를 돌면서 32비트 레지스터에 값을 읽어 일일이 복사하는게 가장 빠릅니다.
물론 mmx 레지스터 이용 등등의 고급기법을 사용하지 않았을때 입니다.(라이브러리는 일반적으로 동작할 수 있어야 하니까 어쩔 수 없습니다.)

memcpy, memmove 소스코드 구해 보면 U, V 등으로 주석을 달아놨는데... 이게 바로 직접 루프돌며 일일이 레지스터에 넣었다가 목적지로 복사하는 코드를 개발하면서 Pentium CPU의 U, V 2개의 파이프를 모두 사용하는걸 표시해 둔겁니다.

소스코드 보시면서 참고하세요.

Necromancer의 이미지

repxx류의 전치명령어들은 cpu내로 들어갈 경우 속도가 더 떨어진다고 합니다.

얘네들은 그다지 사용 빈도가 없기 때문에 실행유닛에서 직접 실행을 못하고
cpu내에 미리 심어져 있는 마이크로코드 시퀀스를 타고 실행하도록 처리되기
때문이죠.

걍 xt나 at시절의 구형 프로그램들을 위해 남겨놓은 거라고 보시면 됩니다.

Written By the Black Knight of Destruction

mithrandir의 이미지

jjjjrr wrote:
안녕하세요
자주질문드립니다
memchr 나 memcpy strstr strcpy 등등의 문자열관련함수들의
내부동작이 어떻게되는지 알고싶은데여
라이브러리구현코드를 구할수는 없나요

glibc 소스 코드를 보시면 되겠군요. 대부분의 리눅스 배포판에 포함되어 있습니다.

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

vuccell의 이미지

strchr strcpy등은 여타 알고리즘과는 전혀 관계없어요..

strchr(char *a, char b)에서
a라는 char형 배열은 이미 메모리에 로드된 상태라..
한바이트 씩 읽으면서 b랑 비교하는게 전혀 느릴이유가.. 없죠..

한 100메가쯤 되는 스트링이라 해도... 0.1초이하 찾을수 있겠죠.. (0.001초라고 할려다.. 테스트하기 귀찮애서 -,-;;; ) 구현방식도 무지 간단합니다 -,-;; 한줄밖에..

void strcpy(char *dest,char *src)
{
        while((*dest++ = *src++) != '\0') ;
}
char *strchr(char *buf, char char_1)
{
        for(;*buf;buf++)  
                if(*buf == char_1)   return buf;
        return NULL;
}

memcpy랑 memcmp는 null terminate check대신 세번째인자의 길이만큼만 한다는 차이만 있을뿐인데..
내부 함수에서 데이터의 유효성은 확인하지 않습니다.
즉 유효하지 않는 처리를 하면, 당연히 에러가 나죠..
(보통 buffer overflow라고 하는... )

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.