PHPとPythonとRubyの連想配列のデータ構造が同時期に同じ方針で性能改善されてた話 - hnwの日記
PHPとPythonとRubyの連想配列のデータ構造がそれぞれ4〜5年ほど前に見直され、ベンチマークテストによっては倍以上速くなったということがありました。具体的には以下のバージョンで実装の大変更がありました。 PHP 7.0.0 HashTable高速化 (2015/11) Python 3.6.0 dictobject高速化 (2016/12) Ruby 2.4.0 st_table高速化 (2016/12) これらのデータ構造はユーザーの利用する連想配列だけでなく言語のコアでも利用されているので、言語全体の性能改善に貢献しています1。 スクリプト言語3つが同時期に同じデータ構造の改善に取り組んだだけでも面白い現象ですが、さらに面白いことに各実装の方針は非常に似ています。独立に改善に取り組んだのに同じ結論に至ったとすれば興味深い偶然と言えるでしょう2。 本稿では3言語の連想配列の従来実
Load-Link/Store-Conditional - Wikipedia
load-link（ロード・リンク、（LL、他に load-linked（ロードリンクト）または load and reserve（ロード・アンド・リザーヴ））と store-conditional（ストア・コンディショナル、（SC）は組み合わせて使用されるコンピュータの命令。これによりロックなしのアトミックなリード・モディファイ・ライト操作[1]が可能となる。 load-link 命令は指定されたメモリ位置の現在の内容を返す。その後の store-conditional 命令は同じメモリ位置へ新たな値を書き込むが、前回の load-link 命令以降にそのメモリ位置の内容が書き換えられていないときだけ書き込みが行われる。何らかの更新がなされていたら、たとえ load-link 命令で読み取った値と同じ内容が書かれていたとしても store-conditional 命令は失敗する。従って、
PythonのJSONパーサのメモリ使用量と処理時間を比較してみる | POSTD
私は、多数の大容量のデータをあちこちに移動させなければならない(クライアント端末をHTTP APIに接続してデータを取得します)ような特殊な使用事例を扱っています。なぜだか ^(1) 、転送形式にはJSONが使われていました。ある時、その大容量のデータが、さらに巨大になったのです。数百メガバイトどころではありません。JSONのデコード処理を実行すると大量のRAMが使用されることが分かりました。たった240MBのJSONペイロードで4.4GBですよ。信じられません。 ^(2) 組み込みのJSONライブラリを使っていて、まず「もっと性能の良いJSONパーサがあるはずだ」と思いました。そんなわけで、計測を始めたのです。 さて、メモリ使用量の計測はやっかいです。 ps コマンドを使ったり、 /proc/<pid> を見たりすることはできますが、断片的なスナップショットが得られるだけで、実際の最大使
C言語でインクルードするだけで使えるNon-movingで正確なコピーGCを作った - Qiita
インクルードするだけで使えるNon-movingで正確なGCをC言語用に作りました。 行数がコメントを除いて100行に満たない非常に小さなライブラリです。 GCのアルゴリズムとしてはCheneyのコピーGCを採用しています。 通常のCheneyのコピーGCではメモリ空間のうち半分が無駄になってしまいメモリ効率が悪かったり、 GC発生時にオブジェクトが移動してしまいC言語のようなポインタを直接触れる言語との相性が悪いという欠点がありました。 今回はヒープ全体を二重連結リストとして管理することでそのような問題を解決しています。 ちなみにこれはTreadmill GCのアイデアと同じです。(が、アルゴリズム自体はTreadmill GCではありません。) APIはLinuxのlist.hに非常に近い見た目になっています。 ある構造体をgcで管理したい場合はstruct gc_head型のメンバを
K&R Malloc解説 - らじうむ覚書
なにか、無闇に時間掛かってしまった･･･ 後で見直して直すと思います。 数あるmallocアルゴリズムの基本であるK&Rのmallocアルゴリズムを解説いたします。 K&Rとは初期のC言語を解説した書籍「プログラミング言語C」(原題:The Programing Language)のことです。 著者であるブライアン・カーニハン氏(Brian W. Kernighan)とデニス・リッチー氏(Dennis M. Ritchie)の頭文字をとってK&Rと呼ばれています。 malloc関数とはヒープ領域から、指定したサイズのメモリを動的に確保する関数です。 C言語などの低レベルの処理を記述する言語では馴染みのある関数です。 Javaなど低レベルの処理を記述しない言語しか使用していない人には、あまり馴染みがないでしょうか？ malloc関数で確保したメモリは対応するfree関数で解放いたします。 明
yebo blog: クヌース教授は間違っていた
2010/06/15 クヌース教授は間違っていた Slashdotによれば、この数十年間、クヌース教授をはじめとするコンピュータ科学者が最適としてきたアルゴリズムを10倍高速にする方法をPoul-Henning Kamp (PHK) というハッカーが見付けたという。その論文タイトルは「You're Doing It Wrong (あなた達のやっている事は間違っている)」で、ACM Queueに掲載されている。別にクヌース教授の考えが間違っているわけではなく、アルゴリズム的には正しいが、実用レベルでは、OSには仮想メモリがあり、VMと干渉しないようにすれば簡単に高性能なシステムが作れる。従来の考え方はモダンな計算機を考慮に入れていないので、現実的には不適合を起こしている。具体的にはヒープにBツリーの要素を取り込んだBヒープというデータ構造を使うことで、バイナリヒープの10倍のパフォーマンスを
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
