16/05/03 20:50:04.37 bxMOJzqX.net
浅野孝夫の『情報の構造』に載っているプログラム例がエレガントで感心した。
921:デフォルトの名無しさん
16/05/04 08:24:35.18 PCMiFBXM.net
>>917-919
ありがとうございます
922:デフォルトの名無しさん
16/05/04 12:49:25.38 A2cfTnr6.net
>>920
浅野孝夫のその本は説明が粗雑なところを詳細なプログラムを読むことで補完しなければならないところが難点。
923:デフォルトの名無しさん
16/05/04 15:23:50.62 OcRpngHJ.net
.>>916
さっぱりわかんね
要するにビットマップで管理するってことか？
勝手にやれとしか
924: ◆tAo.kQ2STk
16/05/04 16:00:56.01 p+LvbHBp.net
>>923
要するに、32ビットのポインタで64GiBの領域を使えるって事
普通は64ビット版のプログラムはポインタを64ビットに拡張するんだけど、
木構造のようなポインタを多用するデータ構造の場合は
32ビット版と比較してメモリの効率が半減するデメリットがある。
この方法だと、メモリ効率を落とさずに4GiBを超えるメモリ領域を同時に使える。
既出かどうか(或いはもっと良い方法があるか)知りたかった
925:デフォルトの名無しさん
16/05/04 16:38:51.07 WruTeJWf.net
アロケータが確保する分にはいいとして、任意のポインタをどう表現するのかねぇ
926: ◆tAo.kQ2STk
16/05/04 17:24:52.95 p+LvbHBp.net
任意のポインタを、アドレスを4ビット右シフトした値として表現する。
ポインタが指す先は常にチャンク境界(16バイト)にアラインメントされてて、
ポインタを使うときは4ビット左シフトしてアドレスに変換してから使う。
「ポインタを変数とかに代入してとっておくこと」と「ポインタをデリファレンスして他所から値を持ってくること」を分けて考えてる。
1バイトが128ビットのマシンだと思えばそんなに変な事ではないかと。
URLﾘﾝｸ(github.com)
927:デフォルトの名無しさん
16/05/04 17:35:44.12 ypA5W//n.net
>>916
よくわかんねーけどやめたら
928:デフォルトの名無しさん
16/05/04 17:37:59.32 WruTeJWf.net
>1バイトが128ビットのマシンだと思えばそんなに変な事ではないかと。
やっぱりそうなるんだ。
ポインタのサイズを節約するために配列や構造体にえらい無駄が出るね。
929: ◆tAo.kQ2STk
16/05/04 17:56:42.05 p+LvbHBp.net
> ポインタのサイズを節約するために配列や構造体にえらい無駄が出るね。
OS内に何らかの言語のインタプリタを実装して、
所謂ユーザーモードで動くプログラムは全てその言語で走る、というのを考えてる。
全てがシェルスクリプト、みたいな感じ。
で、そのインタプリタは数と文字列とハッシュを扱えれば良いと思っていて
ハッシュをAVL、文字列をrope構造なんかの木構造で実装するとすれば
16バイトってサイズは各ノードに情報を格納するのに丁度いいサイズではあるのよ。
ropeってのはこれな。
URLﾘﾝｸ(en.wikipedia.org)(data_structure)
その考えで行くと、あんまり無駄は出ないんじゃないかなとは思う。
勿論実行速度は多少犠牲になるけどね。
930:デフォルトの名無しさん
16/05/04 18:36:41.93 VTHyhTWb.net
>>916
FATの考え方だね。
メモリ管理でも応用できる気はするけど。
931:デフォルトの名無しさん
16/05/04 19:24:52.99 WruTeJWf.net
OSというからmallocとかの話かと思ったら、インタプリタ作ってんのか。
確かにLISPのConsCellの持ち方に似てはいるが。
932:デフォルトの名無しさん
16/05/04 20:55:58.55 I71ZCmWZ.net
16バイト境界でしか返さないmallocを作って４ビットシフトするのとはどう違うのか。
WindowsでいうGlobalAllocしてHANDLEを返して、実際に使うときにはGlobalLockでアドレスにするのと
同じような気がするのだが。
933: ◆tAo.kQ2STk
16/05/04 22:32:04.59 p+LvbHBp.net
>>931
> OSというからmallocとかの話かと思ったら、インタプリタ作ってんのか。
正確には、OSが内部で使うアロケータの話。
malloc/freeとは仕様が違うっていうか前提からして噛み合わない。関数が返す領域のサイズが固定だから。
とここまで書いて、「常に1チャンクだけ確保して返す」とは明確には言ってなかったことに気付いた。ごめんよ。
incしてorするコードが根底にあるから忘れてたわ。
>>932
> 16バイト境界でしか返さないmallocを作って４ビットシフトするのとはどう違うのか。
16バイト境界でしか返さないって条件だと、16バイトの確保の為に追加で8バイトとか必要になる。
malloc/freeの仕様上、どうしても何バイト確保してあるかって情報をヒープ側に保持する必要があるからね。
開放する時点で何バイト確保されているかが自明で、かつ固定長ならば1ビットで済む。
> WindowsでいうGlobalAllocしてHANDLEを返して、実際に使うときにはGlobalLockでアドレスにするのと
操作の意味はそれと同じかも。中身は全然違うだろうけど。
934:デフォルトの名無しさん
16/05/04 23:32:14.08 I71ZCmWZ.net
なんか似たような話を最近見た気がしたがこれだった。
URLﾘﾝｸ(codezine.jp)
935:デフォルトの名無しさん
16/05/04 23:54:19.41 NIqCX6OH.net
ホント最近の記事だな。
936:デフォルトの名無しさん
16/05/05 20:14:53.64 Rts6L3H5.net
浅野孝夫の『情報の構造』の赤黒木のプログラムがすごすぎる。
名人芸の域に達している。
937:デフォルトの名無しさん
16/05/06 02:45:47.47 iu7snuDE.net
>>916
ObjectIDに、32bitメモリアドレスを使っている言語では、
使わない下位4bitを、nil, undefined, true/false などに使っている
938:デフォルトの名無しさん
16/05/10 00:38:26.53 fVgrqlwf.net
gof本の「オブジェクトのクラス」、「パラメータ化」という表現がよくわからん
939:デフォルトの名無しさん
16/05/10 09:44:21.83 vQZ70y3E.net
>>938
よくわからん、じゃねえよ
教えてくださいってちゃんと言えよカス
940:デフォルトの名無しさん
16/05/10 14:50:16.86 bh4nZJj2.net
クラスのインスタンスを引数として渡すってことじゃねーの。
つまりポリモーフィズムよ。