Hatena::ブログ(Diary)

hogeなlog

プロフィール

hogelog

hogelog

小室 直(こむろ すなお)。電気通信大学2003年入学。2010年修士卒業。プログラミングとかしてます。

カレンダー
1984 | 01 |
2006 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2010 | 01 | 06 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 05 | 08 | 09 | 10 | 12 |
2012 | 01 | 04 | 06 |

November 04(Wed), 2009

[][][] 切り出してみる。

要はこういうスタック割り当て、案外便利っすよと。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct Frame {
  struct Frame *prevframe;
  void *top;
  size_t index;
} Frame;
typedef struct Slot {
  void *slot;
  void *last;
  size_t size;
} Slot;
typedef struct Stack {
  Slot *slots;
  size_t slotsnum;
  Frame *lastframe;
  void *top;
  size_t index;
} Stack;

#define STACK_MINSLOTSIZE 1024
static Slot *addslot(Stack *s, size_t slotsize) {
  size_t n = s->slotsnum;
  s->slots = realloc(s->slots, (n+1)*sizeof(Slot));
  s->slots[n].slot = malloc(slotsize);
  s->slots[n].last = (void*)((char*)s->slots[n].slot + slotsize);
  s->slotsnum = n+1;
  return s->slots[n].slot;
}
static size_t stack_grow(Stack *s) {
  size_t nextindex = s->index + 1;
  size_t slotsnum = s->slotsnum;
  if (nextindex >= slotsnum) {
    int i;
    size_t newsize = 0;
    Slot *newslot;
    for(i=0;i<slotsnum;++i) {
      Slot *slot = &s->slots[i];
      newsize += (char*)slot->last - (char*) slot->slot;
    }
    addslot(s, newsize);
  }
  s->index = nextindex;
  s->top = s->slots[nextindex].slot;
  return s->index;
}
void *stack_alloc(Stack *s, size_t size) {
  void *new = s->top;
  void *newtop = (void*)((char*)new + size);
  Slot *curslot = &s->slots[s->index];
  if (newtop > curslot->last) {
    stack_grow(s);
    return stack_alloc(s, size);
  }
  s->top = newtop;
  return new;
}
Frame *stack_newframe(Stack *s) {
  void *ptop = s->top;
  size_t pindex = s->index;
  Frame *f = stack_alloc(s, sizeof(Frame));
  if (f) {
    f->prevframe = s->lastframe;
    f->top = ptop;
    f->index = pindex;
    s->lastframe = f;
  }
  return f;
}
Frame *stack_closeframe(Stack *s) {
  Frame *f = s->lastframe;
  s->top = f->top;
  s->index = f->index;
  s->lastframe = f->prevframe;
  return f;
}
Stack *stack_init(Stack *s) {
  s->slots = NULL;
  s->slotsnum = 0;
  s->lastframe = NULL;
  addslot(s, STACK_MINSLOTSIZE);
  s->index = 0;
  s->lastframe = NULL;
  s->top = s->slots[0].slot;
  s->index = 0;
  return s;
}
void stack_close(Stack *s) {
  int i;
  for(i=s->slotsnum-1;i>=0;--i) {
    free(s->slots[i].slot);
  }
  free(s->slots);
  s->slots = NULL;
}

/** stackalloc test code **/
static int *new_int(Stack *s, const int i) {
  int *dst = stack_alloc(s, sizeof(int));
  *dst = i;
  return dst;
}
typedef struct Array {
  size_t size;
  size_t length;
  char buffer[1];
} Array;
#define array_elem(a, i) ((void*)&((a)->buffer[(a)->size*(i)]))
static Array *new_array(Stack *s, size_t size, size_t len) {
  Array *a = stack_alloc(s, sizeof(Array)+size*(len-1));
  a->size = size;
  a->length = len;
  return a;
}
static Array *new_range(Stack *s, int start, int end) {
  size_t len = end - start + 1;
  Array *a = new_array(s, sizeof(int), len);
  int i;
  for(i=0;i<len;++i) {
    int *p = array_elem(a, i);
    *p = i+start;
  }
  return a;
}
void test01() {
  Stack s_;
  Stack *s = &s_;
  int i, j;
  void *p;
  stack_init(s);
  for(i=0;stack_newframe(s) && i<2;++i) {
    int *sum = new_int(s, 1);
    Array *a = new_range(s, 1, 10);
    for(j=0;stack_newframe(s) && j<10;++j) {
      int *p = array_elem(a, j);
      *sum *= *p;
      printf("%2d(%p) = %7d(%p)\n", *p, p, *sum, sum);
      stack_closeframe(s);
    }
    stack_closeframe(s);
  }
  stack_close(s);
}
int main(int argc, char **argv) {
  test01();
  return 0;
}

がこういう実行結果。

% ./stackalloc
 1(0x99f7030) =       1(0x99f7024)
 2(0x99f7034) =       2(0x99f7024)
 3(0x99f7038) =       6(0x99f7024)
 4(0x99f703c) =      24(0x99f7024)
 5(0x99f7040) =     120(0x99f7024)
 6(0x99f7044) =     720(0x99f7024)
 7(0x99f7048) =    5040(0x99f7024)
 8(0x99f704c) =   40320(0x99f7024)
 9(0x99f7050) =  362880(0x99f7024)
10(0x99f7054) = 3628800(0x99f7024)
 1(0x99f7030) =       1(0x99f7024)
 2(0x99f7034) =       2(0x99f7024)
 3(0x99f7038) =       6(0x99f7024)
 4(0x99f703c) =      24(0x99f7024)
 5(0x99f7040) =     120(0x99f7024)
 6(0x99f7044) =     720(0x99f7024)
 7(0x99f7048) =    5040(0x99f7024)
 8(0x99f704c) =   40320(0x99f7024)
 9(0x99f7050) =  362880(0x99f7024)
10(0x99f7054) = 3628800(0x99f7024)

使いどころは結構あるんじゃないかなー。論文で読んでなるほどなー思って適当に書いてるんだけど、どうなんだろう。メジャーなこういう用途のライブラリ無いのか。


スタック領域そのものをreallocせずにslotとかいう気持ち悪い単位で区切って管理してるのは、アドレス変更されたら嫌だからなんですけど、なんかもうちょいやりようあるような。1024バイトの空のslot一つだけあるときに4096バイトの領域要求したら、1024, 1024, 2048, 4096バイトという4本のslotができて、3つのslotの4096バイトになる領域が無駄になるとか。

あとWORD境界に揃えた方がいいかなーとか。

malloc捨てたりmadviceとかで性能向上とかもすんだろか。やっぱそういうライブラリ無いのか気になる。

mokehehemokehehe 2009/11/04 07:19 興味があるんですが、なんという論文か、あとネットで公開されていたらURLなど教えていただけますか?

pi8027pi8027 2009/11/04 14:57 一部の環境に関して言えば、mmap,mremap でアドレス変更の無い realloc みたいなのが実現できますよ。

kikxkikx 2009/11/04 17:41 obstack みたいなのかな? http://www.gnu.org/software/hello/manual/libc/Obstacks.html

hogeloghogelog 2009/11/04 23:24 >id:mokeheheさん
http://d.hatena.ne.jp/hogelog/20090220/p1 で紹介している論文のことです。この手法を適用することで小さな時間的ロススクリプト言語などのGCをほとんど削減することができるというものです。未踏ユースプロジェクトの「Luaの高速化〜」の主軸となる提案でもあります。で、実装してみたらほんとにGC減ったし処理速度も全然遅くならなそうだし「これいけんじゃね?」というのが http://d.hatena.ne.jp/hogelog/20091022/p1 あたりで示した現状です。僕はLuaで取り組むんですけど、これ他のスクリプト言語でも簡単に適用できんじゃねーかなーという気がしています。

hogeloghogelog 2009/11/04 23:27 > id:pi8027 さん
今回の場合はうーん適用できねーかなーいや一部の環境ではmmapとか使うようにするのかな嫌でもソースコードが#ifdefの嵐になるのはLuaらしくはねーなー、といった感じです。
そんなわけで今回の場合は使えないですが、教えてくれてありがとうございます!

hogeloghogelog 2009/11/04 23:29 > id:kikx さん
コメントに気付くのが遅れましたが、まさにそういうのです! 「そういうのライブラリ無いなら、こういう手法には何か欠点でもあるのだろうか?」と思っていたのでありがたいです。インターフェースなども参考になりますし。あと自分の実装の性能などを計測する対象として。

h_sakuraih_sakurai 2009/11/04 23:56 話が良くわかってませんけど、スタックにメモリ確保といえば alloca
とかがどうのとYTさんが話してました。

hogeloghogelog 2009/11/05 00:40 allocaもスタックにメモリ確保ですね。でもallocaはマシンスタック領域にメモリ確保する命令なんで、スタック伸び縮みが関数呼び出しのそれに合わされてしまいます。
obstackが確保されるのはあくまでヒープ領域です。で、確保と解放がスタックのLIFO的にできるライブラリということです。

mokehehemokehehe 2009/11/05 07:05 >hogelogさん
ありがとうございます!見てみたいと思います。

最近のコメント