이렇게 구현하면 위험할까요? ^^;;

aswip의 이미지

빈번하게 일정한 범위(색인기반)의 데이터를 추가 및 삭제, 그리고 검색이 이루어지는 프로그램을 구현하는 중입니다.
처음에는 std::map 을 고려하였으나, 데이터의 범위가 넓어지면 넓어질수록 추가연산에서 시간이 오래걸리더군요.

어느정도 예상은 하였지만, 이마저도 개선할 수 있는 방법이 없을까.. 고민끝에, 다음과 같이 다소 엉뚱하게
구현하게 되었습니다.

참고로, UserData의 크기는 50 ~ 100 byte 정도입니다.

[1차 시도]

UserData bigDataArray[655360]; // 배열의 Bound는 0부터, 최대 655360까지 보장해야함.

while ( 1 )
{
// Index에 의한 참조로, 검색속도가 보장됨.
UserData &usrData = bigDataArray[ GetUserDataIndex() ];
DoSomething ( userData);
}

위와 같이 구현하게 되면, 컴파일은 되나, Stack Over Flow가 발생하면서, 프로그램이 죽더군요. -_-;;;

[2차 시도]

UserData *pBigDataArray = new UserData[655360];

while ( 1 )
{
// Index에 의한 참조로, 검색속도가 보장됨.
UserData &usrData = pBigDataArray[ GetUserDataIndex() ];
DoSomething ( userData);
}

위와 같이 구현하게 되면, 컴파일 및 실행까지 잘됩니다. 하지만, 무언가 위험해 보이기도 하고, 다소, 무식하게
힙을 사용하는건 아닌지.. ^^

색인의 범위는 0 ~ 655360, 각각의 데이터의 크기는 100 바이트 내/외, 빈번한 추가/삭제/검색시...
위와 같이 구현하면 위험할까요?

조언 부탁드리겠습니다. ^^/

IDNed의 이미지

new의 구현에 따라 달라진다고 생각합니다.(라이브러리상의 구현 뿐만 아니라 힙 관련 커널의 구현 등)
즉 힙 사용시 allocate-on-write(그냥 copy-on-write 보고 용어 따라했습니다 ㅋㅋㅋㅋ)가 된다면 채 메모리가 다 할당되지 않아도 힙이 사용되고, 어느정도 한계를 넘으면 스택오버같이 처리해주어야겠지요.
표준에 다 할당해야 한다는 규정이 있나요? 그건 저는 잘 몰라서 -_- 틀릴수도 있겠네요.

어쨌든 처음부터 다 할당한다면, 할당실패시 bad_alloc만 잡아 주면 되지 않을까요. 그거야 언어에서 표준으로 보장한 내용이니 bad_alloc만 사용하면 문제가 없을 것입니다.

kewlbear의 이미지

hash_map(비표준이지만 대부분 지원)이나 unordered_map(표준이지만 컴파일러가 지원하지 않을 가능성 많음)을 고려해 보시는 것은 어떨까요?

gimmesilver의 이미지

삽입/검색 성능 최대를 목적으로 한 것이라면 상관없습니다.
다만 IDNed님 말씀처럼 메모리 할당 실패에 대한 고려는 해야 겠지요...
다만 위의 방법은 UserData라는 구조체에 별도의 flag가 없다면 실제 해당 인덱스 값이 유효한지 여부는 알기 힘들겠군요. 그리고 실제 유효하지 않은 데이터도 미리 메모리를 할당하기 때문에 메모리 오버 헤드가 있는 정도입니다. 하지만 UserData 크기가 100bytes 정도라고 한다면 전체 할당 크기는 65Mbytes 정도이므로 그다지 큰 오버헤드는 아닙니다.

------------------------
http://agbird.egloos.com

김성진의 이미지

빈번한 삭제, 삽입이 의미하는 것은 동시에 655360개의 entry가 모두 존재하는 것은 아니겠지요?

평균 전체 entry 갯수에서 20%정도의 데이타가 존재한다고 가정하면,

위와 같이 코딩 방법은 세련된 것은 아니라고 생각됩니다.

물론, 관점에 따라 다르겠지만, 만일 제 팀의 팀원이 이렇게 코딩한다면 제게 혼났을 겁니다.

위와 같은 요구에 대한 검색은 운영체제의 MMU 구현을 참조하시면 좋을 듯 합니다.

특정 페이지가 할당되었는지 아닌지를 MMU는 매번 판단을 해야 하는데,

이때 2중 혹은 3중 맵을 사용합니다. (공식적으로 지칭하는 이름이 기억이 안나는군요..)

저는 그것을 추천드립니다.

고도의 추상화, 극도의 구체화, 에디슨을 그리워하다.

댓글 달기

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