X

結局C++とRustってどっちが良いの？ 2traits

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
垢版 |
2023/04/02(日) 00:42:57.53ID:W9/nq+tL
「C++の色々配慮してめんどくさい感じは好きだけど、実務になったらメモリ安全性とか考えて今後Rustに変わっていくんかな」
「うだうだ言ってないで仕事で必要なのをやればいいんだよ、趣味なら好きなのやればいい」

っていうスレ。

前スレ: 結局C++とRustってどっちが良いの？
https://mevius.5ch.net/test/read.cgi/tech/1677286186/
0680デフォルトの名無しさん
垢版 |
2023/04/28(金) 07:29:21.75ID:tvIf37hb
>>678
>キャッシュは、そういう問題じゃなく、前に何をやったかによって、
>キャッシュに乗るかどうかが変わってくると言うことが起きることを
>「ケースバイケース」と言っている。
君がそう思って書いてるのはわかってるよ
それが的外れだから勉強したほうがいいよと言ってるんだよ

> 必ず隣り合う前後を交換することを２個おきにやった場合の集合を最初から最後まで巡る場合
この処理がvectorより速くなるとでも？
遅い速いは相対的なものなんだから何と比べてるかくらいはわかるでしょ？
0681デフォルトの名無しさん
垢版 |
2023/04/28(金) 08:50:10.99ID:gH8UoCJq
Rustはグラフ的な構造が作れないから
単純な構造しか扱わないシステムプログラミングにはC++より
優れてると思う
0683デフォルトの名無しさん
垢版 |
2023/04/28(金) 09:39:41.22ID:ypH1tIw5
>>681
そのへんはどの言語も同じ
作れないとか優劣とかない
言語よりアルゴリズムの差が大きい
0684デフォルトの名無しさん
垢版 |
2023/04/28(金) 10:57:08.12ID:pksuSfee
Rustは、要素のラベルとしてindexを使うが、indexは初心者でも理解し易い。
ところが、C++は、要素のラベルとしてpointerを使う。
pointerを理解できない人は、いつまでもindexを使おうとする。
それでC++の本来の性能が出ないので、C++はRustよりunsafe
と思い込むが、実際はその人の使い方が未熟だからに過ぎない。
多くはC++のせいではなく、その人がまともに使いこなせて無い事が原因。
0686デフォルトの名無しさん
垢版 |
2023/04/28(金) 12:39:05.67ID:35xT11dO
>>671
vectorの使い方すら知らないのかよ
プログラムを書いたことがないんだな
次の要素や前の要素を指すにはindexを増減させるのではなく
イテレータを使いポインタでアクセスだ
次の要素を指すには++で要素の大きさ分が加算されるだけなので速い
0687デフォルトの名無しさん
垢版 |
2023/04/28(金) 12:52:16.57ID:35xT11dO
>>678
linked listのワーストケースはその通りキャッシュが効かず順にたどるのも遅くなる
そこまでわかっているならvectorが速いことも理解できるだろ
0688デフォルトの名無しさん
垢版 |
2023/04/28(金) 12:54:59.10ID:l8aVe0s/
>680
>> 必ず隣り合う前後を交換することを２個おきにやった場合の集合を最初から最後まで巡る場合
>この処理がvectorより速くなるとでも？
>遅い速いは相対的なものなんだから何と比べてるかくらいはわかるでしょ？
>686
>イテレータを使いポインタでアクセスだ

コードを晒すのはやめるけど、カスタムリストのポインタ操作で実装したらリストの方が速かった
sizeof(foo)= 256 back swap
std::vector, swap(xs[i],xs[i+1]) 55 15
std::vector, swap(*it1,*it2) 54 15
std::list, swap(*it1,*it2) 22 15
LinkList, modify prev/next 22 4
0689デフォルトの名無しさん
垢版 |
2023/04/28(金) 13:04:21.51ID:l8aVe0s/
backは末尾追加(push_backでもemplace_backでも同じ)
swapは>>678が言っている「必ず隣り合う前後を交換することを２個おきにやった場合の集合を最初から最後まで巡る場合」

試してみたら言っている通りだったけど、256バイトなのが効いている結果だと思う
それとstd::listはポインタ操作をやらせてくれなのかな？
0690デフォルトの名無しさん
垢版 |
2023/04/28(金) 13:12:38.01ID:lHXn1lC8
デカいものはそのようなそれ自体を動かすことはしない
例えばソートする場合でもポインタもしくはインデックスだけをソートする
0694デフォルトの名無しさん
垢版 |
2023/04/28(金) 17:25:35.41ID:0xBJDLDh
ポインタのインスタンス、だろ。リリースビルドではポインタだけになってるかもしれないけど。
0695デフォルトの名無しさん
垢版 |
2023/04/28(金) 18:50:51.20ID:rYsqY01x
そのvectorに格納している要素が大きな実体なのかそこへのポインタ(アドレス)なのかを理解していないとまずいぜ
要素がポインタを含めて小さい実体ならばvectorの要素の入れ替え・挿入・削除は非常に速い
0697デフォルトの名無しさん
垢版 |
2023/04/28(金) 19:07:38.08ID:aOCxNlg7
scanは先頭からvalue(int 4Byte)にアクセスしてダミーXOR演算する処理
dual link listのポインタ操作版(LinkList)はswapした後のscanが256Byteで激落ちだった xx
ForwardLinkListはforward linkかつallocate時のnextを別途キープし続けるデータ構造

sizeof(foo)= 256 n=1000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 52.986 3.461 14.739 3.458 74.644
std::list, swap(*it1,*it2) 22.574 6.470 16.252 6.375 51.672
LinkList, modify prev/next 21.940 6.509 4.229 39.717 72.395 xx
ForwardLinkList, modify next 22.824 6.532 4.395 5.861 39.611 *

sizeof(foo)= 128 n=2000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 60.411 6.789 14.340 7.144 88.683
std::list, swap(*it1,*it2) 28.981 13.839 16.871 14.124 73.815
LinkList, modify prev/next 27.969 13.845 10.074 16.062 67.951 *
ForwardLinkList, modify next 28.204 13.980 9.802 13.791 65.778 *

sizeof(foo)= 64 n=4000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 62.683 7.733 14.140 7.768 92.325
std::list, swap(*it1,*it2) 35.496 14.177 18.950 14.136 82.759 *
LinkList, modify prev/next 32.240 14.129 19.082 14.404 79.856 *
ForwardLinkList, modify next 33.547 14.197 19.169 13.922 80.835 *

sizeof(foo)= 32 n=8000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 61.452 8.084 14.104 8.230 91.870 *
std::list, swap(*it1,*it2) 51.176 17.195 22.936 17.336 108.643
LinkList, modify prev/next 47.231 17.226 23.422 17.519 105.398
ForwardLinkList, modify next 48.123 17.387 23.529 17.408 106.447
0698デフォルトの名無しさん
垢版 |
2023/04/28(金) 19:11:25.99ID:aOCxNlg7
C++側としては面白がって人の作ったベースを弄り始めたんだけれど、
sortしたり途中挿入削除しないリニアアクセスだけの問題ならどっちでも良いなw

ただし要素が小さくて途中挿入削除しないのならvector

sizeof(foo)= 16 n=16000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 61.891 9.511 13.994 9.677 95.074 **
std::list, swap(*it1,*it2) 90.948 22.966 34.215 23.463 171.592
LinkList, modify prev/next 76.692 22.989 32.457 23.262 155.400
ForwardLinkList, modify next 76.857 23.095 31.426 23.639 155.018

sizeof(foo)= 8 n=32000000 back -> scan -> swap -> scan = total
std::vector,swap(*it1,*it2) 63.911 9.002 14.222 8.933 96.068 ***
std::list, swap(*it1,*it2) 171.875 52.681 71.011 43.465 339.032
LinkList, modify prev/next 142.104 39.655 52.617 40.589 274.964
ForwardLinkList, modify next 141.527 39.843 49.236 39.779 270.385

>>696に同意です
0700デフォルトの名無しさん
垢版 |
2023/04/28(金) 20:00:39.11ID:EmUQPNaW
>>694
メンバにサイズデカいのがあったら
moveコン呼ばれても結局コピーが発生するね
訂正訂正！
0701デフォルトの名無しさん
垢版 |
2023/04/28(金) 20:16:09.12ID:Du1IZbO4
moveがコピーをしないという意味のコピーと
今話題になっている入れ替えたりズラしたりする時にコストとなるコピーは別物だろ

moveでもコピーコストは発生する
それがポインタならばそのコピーコストが最小限になるというだけだ
0702デフォルトの名無しさん
垢版 |
2023/04/28(金) 22:34:19.60ID:/wnDoHyX
>>684
RustもC++と同じだよ
例えばvec.iter()はvecの各要素への参照(ポインタ)列を返すイテレータ
例えば要素のkey1をキーとしてソートするなら
vec.iter().sorted_by_key(|x| x.key1)
これもvecの各要素への参照(ポインタ)列をソート順に返すイテレータ
いずれも各要素自体のコピーは発生しない
0705デフォルトの名無しさん
垢版 |
2023/04/29(土) 01:18:03.83ID:yAVCYP8x
そうじゃなくて頭から最後まで要素を一回走査して挿入削除する場合は一回当たりのコスとはvectorより有利
何度も何度も繰り返し頭から走査する条件下では不利
ここでのベンチ結果は後ろのパターンばかりで不利になるのは当然

コード書いてる人が意図的に間違えてるのかセンスがないかのどちらか
アルゴリズムの意味が理解できてないと言う話
0706デフォルトの名無しさん
垢版 |
2023/04/29(土) 01:21:50.87ID:yAVCYP8x
コードを書く人間として常識的に考えればわかる
挿入時に一部だけ鎖つなぎなおすのが低コストか
毎回全部後ろまでずらすのが低コストか

削除時に一部だけ鎖つなぎなおすのが低コストか
毎回全部後ろの要素を前へずらすのが低コストか
0708デフォルトの名無しさん
垢版 |
2023/04/29(土) 01:52:27.12ID:QawJMl68
実際に色んな仕事をしたことある人たちがvector派という感じ
現実は挿入することが目的ではなくその後に使うところが本場でvectorが有利
稀に比較挿入が主たる場合もあるけど効率の悪いlinked listではなくbinary treeなどを使う
0710デフォルトの名無しさん
垢版 |
2023/04/29(土) 06:10:16.91ID:g1O4sC7f
>>705
> 頭から最後まで要素を一回走査して挿入削除する場合は一回当たりのコスとはvectorより有利

そのような走査して挿入する利用で最も多いのが何かの順序に並べるケース
その場合は結果的にソートをしていることになるがオーダーO(n^2)となり効率が悪い

効率が良い方法はvectorを利用してまずは順序関係なく要素を追加してしまい
その格納された各要素へのポインタを対象に一気にO(n·log(n))の速いソートするとよい
ソートを必要とする多くのデータ処理はそのようにvectorを利用する形になる
0711デフォルトの名無しさん
垢版 |
2023/04/29(土) 06:57:32.23ID:DIPSnmX9
なんでソート済みのなかに挿入するのにまたソートするの？
頭悪そう。
0712デフォルトの名無しさん
垢版 |
2023/04/29(土) 06:58:38.69ID:x0nehzJt
だってほら、ソート済みのオブジェクトをひっかきまわす別スレッドがあったり?ｗ (ひっかきまわし
0713デフォルトの名無しさん
垢版 |
2023/04/29(土) 07:43:01.19ID:7W8CIlYn
Linked Listをソートに使うのはアホ
計算量オーダーを知らないアホ
既に順に並んでるところへ挿入していくから速そうだと勘違いするアホ発見器
0714デフォルトの名無しさん
垢版 |
2023/04/29(土) 08:07:10.82ID:qQ47Kbbt
>>703
節約できてねーよw
0715デフォルトの名無しさん
垢版 |
2023/04/29(土) 08:11:13.42ID:zSimqKUs
>>706
そこはみんなわかってるよ
挿入時や削除時に挿入位置と削除位置を見つけるために
LinkedListの走査が必要な使い方をしたら
性能的にはLinkedListを使う価値がなくなるという話をみんなしてるんだよ
0718デフォルトの名無しさん
垢版 |
2023/04/29(土) 10:31:22.19ID:7o70JIXk
自分の無知を知らずシッタカするド素人と
自分の無知を察して慎重にシッタカするド素人
自分の無知を察して口をつぐむ慎ましいド素人

三番目なのがRustユーザ
0719デフォルトの名無しさん
垢版 |
2023/04/29(土) 11:02:19.50ID:YiZx6les
QiitaなんかでRustポエムがいいね入れ食いなのから察するに
Rustユーザは>>563みたいな数独パズル状態でどん詰まり傾向かな？
0720デフォルトの名無しさん
垢版 |
2023/04/29(土) 11:12:39.77ID:ohv1w+T9
結局、ここに溜まるような奴はみんな、やれといわれたら(どっちもちゃんと)やる人間だろうしね

でも好きずきはある やっぱ俺はC++が好き
0721デフォルトの名無しさん
垢版 |
2023/04/29(土) 11:22:17.96ID:dmw04PPX
いやmoveを分かってないレベルのRustユーザがいる
おそらくQiitaでRustポエムをいいねしてる？

一方、C++ユーザは実動コードやらベンチ結果を晒して議論するのを面白がってる様子
どっちも無知でも、どっちが成長するのか目に見えてるなw
0723デフォルトの名無しさん
垢版 |
2023/04/29(土) 11:36:22.20ID:7o70JIXk
言語としてはある種似てるとは思うわ
言語仕様としてではなくてね
HaskellとC++とRustはいっしょのカテゴリに入ってる
シッタカしたいタイプのド素人がドヤるための言語
JavaとかPHPをドカタ言語といって蔑むのといっしょ
女さんが自分を飾るブランドを選ぶのといっしょ
0724デフォルトの名無しさん
垢版 |
2023/04/29(土) 11:42:46.52ID:yAVCYP8x
>>710
違うよ
何かを順番に並べるケースは実際はランダムアクセスなんだよ
そんな簡単なこともわからないの？
0726デフォルトの名無しさん
垢版 |
2023/04/29(土) 11:52:16.10ID:yAVCYP8x
>>710
＞　そのような走査して挿入する利用で最も多いのが何かの順序に並べるケース

頭から走査する回数が増えるとlinkedlistが極端に不利になるって常識的に分かるよね
そういう条件でソートをlinkedlistでやるやつは馬鹿だろ
それなのに何で頭から操作繰り返すアルゴリズムを選ぶのか？
意味分かってないのか？
0727デフォルトの名無しさん
垢版 |
2023/04/29(土) 11:59:53.23ID:yAVCYP8x
>>725
結果見れば分かるだろ

結果から見るとlinkedlistで単体の件で条件マッチするまでソートはランダムソートのコスト＋比較だから

a[x] で仮に条件が合うのがｋだとしてそこまでは実際ランダムアクセスでそこまで行ってるのと変わらない
数学の素養がないのは君なんだけど…

多分これを書いても理解できてないよね…
0731デフォルトの名無しさん
垢版 |
2023/04/29(土) 12:03:17.50ID:yAVCYP8x
ランダムアクセスが苦手なのに挿入のたびに実質ランダムアクセスさせられてる
それに気が付いてない人の多いこと

全件を一度走査するのと実質ちまちまランダムアクセスを繰り返す挿入ソートの違いが理解できない馬鹿頭

数学が出来ない人間と話をしても無駄なんだよな…
馬鹿は水掛け論だと誤解してるから…
0736デフォルトの名無しさん
垢版 |
2023/04/29(土) 12:11:44.15ID:MIzfr5va
ようやく理解できた
局所的に見るとlistが速い部分もあるんだけど
作業全体で比較するとvectorが速くなるってことか
0737デフォルトの名無しさん
垢版 |
2023/04/29(土) 12:13:24.42ID:yAVCYP8x
変な話だけど多分この議論の勝者は俺なんじゃないかな
数学的素養のない人間に衝撃を与えてる
0741デフォルトの名無しさん
垢版 |
2023/04/29(土) 12:25:50.80ID:OSQfAzE+
ちょっと再帰型の例として単方向連結リストが出ただけでここまで話を脱線させることができる集団
0742デフォルトの名無しさん
垢版 |
2023/04/29(土) 12:35:51.92ID:L+mlGJh3
>>735
他の人たちの説明はほぼわかったけど
きみの説明だけわからんかった
具体的なコードを出してみたらどう？
0744デフォルトの名無しさん
垢版 |
2023/04/29(土) 13:08:56.23ID:cwi8dy59
>話を脱線させることができる集団

やっぱり、LinkedListの無理問答は脱線の仕掛けだったんだ
0745デフォルトの名無しさん
垢版 |
2023/04/29(土) 13:33:17.72ID:Tjp8jVNl
論理的思考というワードを見るとなぜかテンションが上がる
所有権複製と同じぐらい

プログラムが論理的かどうかを判断するだけなら思考を研究しなくていい
最近のAI界隈が脳科学の研究をしないのと同じ
0747デフォルトの名無しさん
垢版 |
2023/04/29(土) 14:41:05.09ID:20ghSNY5
>>745
>プログラムが論理的かどうか
論理もへったくれもないこと言ってんな
どんなにトチ狂った論理でも論理は論理だし
プログラムには論理以外何も無い
何が言いたいんだこいつは
0749デフォルトの名無しさん
垢版 |
2023/04/29(土) 16:48:28.13ID:ohv1w+T9
本質的に雑スレなので、C++ vs Rust みたいな話題が好きそうな人が好きそうな話題ならなんでもいいや
0751デフォルトの名無しさん
垢版 |
2023/04/29(土) 17:04:51.89ID:LRGNcJXi
正直リンクドリストなんて一生使わないので興味ないのは図星
0752デフォルトの名無しさん
垢版 |
2023/04/29(土) 19:05:39.22ID:805CSB5r
>>739
そのコムソートのためにnとmの2つのポインタを持って、
双方向リストでmとnの入れ替えをしようとしたら、
ノードの入れ替えだけでとんでもないコストになった。
読み出しが4回と書き込みが8回もかかる

# mの前後がnを指すようにする
読　m_prev = m->prev
書　m_prev->next = n
読　m_next = n->next
書　m_next->prev = n

# nの前後がmを指すようにする
読　n_prev = n->prev
書　n_prev-> next = m
読　n_next = n->next
書　n_next->prev = m

# mがnの前後を指すようにする
書　m->prev = n_prev
書　m->next = n_next

# nがmの前後を指すようにする
書　n->prev = m_prev
書　n->next = m_next

リストのノードの入れ替えがこれだけ高コストだと、
ノードを入れ替えずに格納している要素の入れ替えをしたほうがよくて、
要素のサイズが大きければポインタのみ収容したほうがよくて、
ベクタが有利になるポインタのみ収容に行き着いてしまう？
0753デフォルトの名無しさん
垢版 |
2023/04/29(土) 19:15:52.32ID:XcHaQTov
>>752
ベクタの値の交換とどっちが高コストかはその値のサイズによるでしょ。
値の交換はリンクトリストでもできるわけだからコストの低い方を選べばいい。
0754デフォルトの名無しさん
垢版 |
2023/04/29(土) 19:31:19.50ID:s2+5kMs9
ベクタでソートする時は要素を動かす必要はなく各要素を指すポインタをソートする
リストでも同じ方法が可能だがリンクを毎回たどる分だけ不利
領域分割のクイックソートなどもリストでは使えない
0755デフォルトの名無しさん
垢版 |
2023/04/29(土) 19:41:23.91ID:IKRrkEkG
なんでソートする必要のあるデータを連結リストにぶち込もうと思ったんですか？
0756デフォルトの名無しさん
垢版 |
2023/04/29(土) 20:12:09.35ID:XcHaQTov
>>754
リンクを毎回たどるって何のことを言ってんの？>>739のように現在指している要素の隣の要素を参照するだけだよ。

>領域分割のクイックソートなどもリストでは使えない

クイックソートもインデックスでランダムアクセスが必須じゃないからリンクトリストでもいけるみたい。
最初のピボット選択に不利なくらいで。
0760デフォルトの名無しさん
垢版 |
2023/04/29(土) 21:28:35.35ID:OSQfAzE+
最悪計算量がO(1)の両端キューがどうしても欲しい場合にでも使えばいいんじゃないでしょうか
0761デフォルトの名無しさん
垢版 |
2023/04/29(土) 21:36:10.77ID:ohv1w+T9
まあ、linked list でいっかあ、ってとき。簡単なのはメリット。
おいおい、ちゃんとしたコンテナに替えてもよし。
0762デフォルトの名無しさん
垢版 |
2023/04/29(土) 21:52:36.29ID:8bsno8eR
両端キュー(deque)はリストではなくベクタ系による実装の方が好まれて使われる
std::dequeue、JavaのArrayDequeue、RustのVecDequeなど
0763デフォルトの名無しさん
垢版 |
2023/04/29(土) 22:13:48.24ID:fyMAdwwx
chatgptにlinked listがいい例を挙げてもらった
テキストエディタ、ジョブスケジューラ、メモリ管理、ハッシュテーブル
0764デフォルトの名無しさん
垢版 |
2023/04/29(土) 22:15:45.27ID:2xE5oJ1V
>>756
>リンクを毎回たどるって何のことを言ってんの？>>739のように現在指している要素の隣の要素を参照するだけだよ。
LinkedListでリンクをたどらずどうやって隣の要素を参照するのか教えてくれるかな？
0765デフォルトの名無しさん
垢版 |
2023/04/29(土) 22:23:38.61ID:XcHaQTov
>>755
ベクタ/リストをソートするのに計算量的な差は特にない。
ソート済みのものに要素を挿入するのは一長一短あるが一般にはリストが有利な場合が多いな。
挿入自体のパフォーマンスに特化するなら場合はヒープのような木構造を使うのがベストだろうが。
0767デフォルトの名無しさん
垢版 |
2023/04/29(土) 22:26:27.79ID:RlwUT4Ts
>>763
ハッシュテーブルでもリンクリストを使うチェーン法はリンクをたどるコストが無駄なので避けられる
現実的に効率の良いオープンアドレス法が好まれておりベクターが使われている
0768デフォルトの名無しさん
垢版 |
2023/04/29(土) 22:39:43.93ID:7o70JIXk
なんか偶然ソートの話になってるけど
流れを読んでからこれ書いたんじゃなくて
「ところでインサーションソートなんてベクタじゃ苦しいだろうけど
リストならすごく効率がいいんではないか？　を確かめようとしたら
list::sortがおそらくすでに十分に効率的に書かれてることが分かって
インサーションソートを自分で実装する気が萎えた
（いちおう拾ったコードは乗せてあるけどクッソ遅い）」という別の話

https://ideone.com/D9ljA7
function asc desc shuf
std::sort(v) 16 13 72
list::sort 43 60 332　←十分早い
std::qsort(v) 47 45 144　←参考
0769デフォルトの名無しさん
垢版 |
2023/04/29(土) 22:50:51.62ID:hqB48CC6
>>766
リンクをたどらず隣の要素を参照することはできないのね
チューリング賞ものの新アルゴリズムでもあるのかと思って期待しちゃったよ
数学的に
0773デフォルトの名無しさん
垢版 |
2023/04/30(日) 00:02:56.42ID:0nNhKOfm
Microsoft's adoration of Rust does have limits.
"Rewriting Windows in Rust probably isn't going to happen anytime soon," said Weston,
"so while we love Rust, we need a strategy that also includes securing more of our native code."
0775デフォルトの名無しさん
垢版 |
2023/04/30(日) 01:22:44.98ID:bU1qZ3nv
>>769
LinkedListにおいて、キャッシュに載っていれば隣の要素は、1クロックで
辿れるから何の問題もない。アセンブリコードは、
mov rbx,[rbx + pNext]
みたいになり、キャッシュに載っていれば1クロック。
多くの場合、キャッシュに載っていることが多い。
乗っていない場合は、prefetch 命令で載せることができる。
0776デフォルトの名無しさん
垢版 |
2023/04/30(日) 01:28:36.62ID:bU1qZ3nv
Stroustrup氏は、キャッシュミス時のハードウェアによる自動 prefetch が
数百クロックかかると書いていたが、それは過去の話で、
現在の DDR4-SDRAM だと、15クロックだと聞いた。
だから、キャッシュに載ってなくても15クロックのペナルティーで済む。
また、pNext を読む前に prefetch 命令で pNext の部分をキャッシュに読み込ます
ようにしておけば、ペナルティーは 1 クロック以下に近くなる。
「以下」と書いたのは、いまの CPU は複数命令の同時命令実行機能が有るので
prefetch命令自体は0クロックで実行できることがあるから。
0777デフォルトの名無しさん
垢版 |
2023/04/30(日) 01:38:31.10ID:RN/WMs5a
ほんと頭悪すぎだろ
数学的に
0778デフォルトの名無しさん
垢版 |
2023/04/30(日) 01:38:51.52ID:bU1qZ3nv
なお、LinkedListでも多くの場合は、次のノードは、アドレスがほぼ隣接しているので
キャッシュに載っている確率が高い。ほぼ連続的なアドレスを次々に辿っていくので
ほとんどの場合、LinkedListのノードは読み込み時にキャッシュに載り続けている。
10万個の要素があった時、その内、2つの要素を10回交換したとしても、
キャッシュの乱れは、40回程度。10万要素の内の40回程度、キャッシュ
ナルティーが生じるだけ。
それぞれが15クロックほど遅くなるだけだから、10万個の要素を辿っても、
全体として、600クロックほど、キャッシュ読み込みの時間が追加されるだけ
のはず。ただし、キャッシュミス時の自動prefetchの時間が15クロック
かどうかは不明。
なお、ソフトウェア的にprefetch命令をマシン語で書いておけば、他の命令を
実行中にprefetch動作が入るので、キャッシュペナルティーを実質0クロック
にできる。
0780デフォルトの名無しさん
垢版 |
2023/04/30(日) 01:44:17.33ID:bU1qZ3nv
ここの人は何か勘違いしてるようだが、LinkedListで隣のノードに辿るのは、
C で書くと
pNode = pNode->pNext;
という1行で書けるが、アセンブリだと、
mov rbx,[rbx + (pNextのオフセットアドレス)]
という 1命令になって、1クロックに過ぎない。
一方、配列の場合の、++ptr は、
add rbx,(1要素のバイト数)
という1命令で書けて、これも1クロック。

なので、キャッシュミスがない限り、LinkedListも配列と同じ速度で
ノードを辿っていける。
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況