-
Notifications
You must be signed in to change notification settings - Fork 0
/
Swap-functions.html
488 lines (405 loc) · 18.3 KB
/
Swap-functions.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Swap実装の効率性と非効率性の完全な説明</title>
<style>
body {
font-family: Arial, sans-serif;
line-height: 1.6;
color: #333;
max-width: 800px;
margin: 0 auto;
padding: 20px;
}
h1, h2 {
color: #2c3e50;
}
table {
width: 100%;
border-collapse: collapse;
margin-top: 20px;
}
th, td {
border: 1px solid #ddd;
padding: 12px;
text-align: left;
}
th {
background-color: #f2f2f2;
}
svg {
max-width: 100%;
height: auto;
}
</style>
<script src="https://cdn.rawgit.com/google/code-prettify/master/loader/run_prettify.js"></script>
</head>
<body>
<h1>Swap実装の効率性と非効率性の完全な説明</h1>
<h2>1. データ構造の説明</h2>
<h3>1.1 swap1 (スタックベース)</h3>
<p>
- 一時的な配列 <code>char temp[size]</code> をスタック上に確保<br>
- バイト単位でデータをコピー
</p>
<h3>1.2 swap2 (ヒープベース)</h3>
<p>
- 一時的な配列 <code>char *temp</code> をヒープ上に動的確保<br>
- <code>memcpy()</code> 関数を使用してデータをコピー
</p>
<h3>1.3 swap3 (sys/queue.hベース)</h3>
<p>
- <code>sys/queue.h</code> で定義されたリスト構造を使用<br>
- <code>struct listitem</code> にデータへのポインタと大きさを保持<br>
- リスト要素間でポインタを交換
</p>
<h2>2. メモリレイアウトの比較</h2>
<svg width="700" height="300" xmlns="http://www.w3.org/2000/svg">
<style>
text { font-family: Arial; font-size: 14px; }
.title { font-weight: bold; font-size: 16px; }
</style>
<!-- スタックベース -->
<g transform="translate(0,0)">
<text x="10" y="20" class="title">スタックベース (swap1)</text>
<rect x="10" y="30" width="200" height="50" fill="#FFB3BA" stroke="black" />
<text x="15" y="60">データA</text>
<rect x="10" y="90" width="200" height="50" fill="#BAFFC9" stroke="black" />
<text x="15" y="120">データB</text>
<rect x="10" y="150" width="200" height="50" fill="#BAE1FF" stroke="black" />
<text x="15" y="180">一時バッファ</text>
</g>
<!-- ヒープベース -->
<g transform="translate(250,0)">
<text x="10" y="20" class="title">ヒープベース (swap2)</text>
<rect x="10" y="30" width="200" height="50" fill="#FFB3BA" stroke="black" />
<text x="15" y="60">データA</text>
<rect x="10" y="90" width="200" height="50" fill="#BAFFC9" stroke="black" />
<text x="15" y="120">データB</text>
<rect x="10" y="150" width="200" height="50" fill="#BAE1FF" stroke="black" />
<text x="15" y="180">動的割り当てバッファ</text>
</g>
<!-- queueベース -->
<g transform="translate(500,0)">
<text x="10" y="20" class="title">queueベース (swap3)</text>
<rect x="10" y="30" width="180" height="30" fill="#FFB3BA" stroke="black" />
<text x="15" y="50">データA</text>
<rect x="10" y="70" width="180" height="30" fill="#BAFFC9" stroke="black" />
<text x="15" y="90">データB</text>
<rect x="10" y="110" width="80" height="30" fill="#BAE1FF" stroke="black" />
<text x="15" y="130">ポインタA</text>
<rect x="110" y="110" width="80" height="30" fill="#BAE1FF" stroke="black" />
<text x="115" y="130">ポインタB</text>
<path d="M50,140 L50,170 L100,170 L100,50" fill="none" stroke="black" stroke-dasharray="5,5" />
<path d="M150,140 L150,190 L200,190 L200,90" fill="none" stroke="black" stroke-dasharray="5,5" />
</g>
</svg>
<h2>3. 操作の比較</h2>
<table>
<tr>
<th>実装</th>
<th>操作手順</th>
<th>効率性</th>
</tr>
<tr>
<td>スタックベース (swap1)</td>
<td>
1. 一時バッファにAをコピー<br>
2. AにBをコピー<br>
3. Bに一時バッファをコピー
</td>
<td>データサイズに比例して遅くなる</td>
</tr>
<tr>
<td>ヒープベース (swap2)</td>
<td>
1. ヒープ上に一時バッファを確保<br>
2. 一時バッファにAをコピー<br>
3. AにBをコピー<br>
4. Bに一時バッファをコピー<br>
5. 一時バッファを解放
</td>
<td>データサイズに比例して遅くなる<br>メモリ割り当てのオーバーヘッドあり</td>
</tr>
<tr>
<td>queueベース (swap3)</td>
<td>
1. ポインタAとポインタBを交換
</td>
<td>データサイズに関係なく一定時間</td>
</tr>
</table>
<h2>4. なぜqueueベース (swap3) が効率的か</h2>
<ol>
<li><strong>データコピーの回避：</strong> 実際のデータをコピーせず、ポインタのみを交換します。</li>
<li><strong>一定時間操作：</strong> データサイズに関係なく、常に同じ時間で操作が完了します。</li>
<li><strong>メモリアクセスの最小化：</strong> ポインタの交換のみなので、大量のメモリアクセスを避けられます。</li>
<li><strong>追加のメモリ割り当て不要：</strong> 一時的なバッファを必要としないため、メモリ管理のオーバーヘッドがありません。</li>
<li><strong>キャッシュ効率：</strong> 少ないメモリアクセスは、キャッシュの効率的な利用につながります。</li>
</ol>
<h2>5. なぜ他のSwap実装がQueueベースと比べて遅いのか</h2>
<h3>5.1 スタックベース (swap1) の問題点</h3>
<svg width="600" height="300" xmlns="http://www.w3.org/2000/svg">
<style>
text { font-family: Arial; font-size: 14px; }
.title { font-weight: bold; font-size: 16px; }
</style>
<text x="10" y="20" class="title">スタックベース (swap1) の動作</text>
<!-- データA -->
<rect x="10" y="40" width="180" height="40" fill="#FFB3BA" stroke="black" />
<text x="15" y="65">データA</text>
<!-- データB -->
<rect x="10" y="90" width="180" height="40" fill="#BAFFC9" stroke="black" />
<text x="15" y="115">データB</text>
<!-- 一時バッファ -->
<rect x="10" y="140" width="180" height="40" fill="#BAE1FF" stroke="black" />
<text x="15" y="165">一時バッファ</text>
<!-- 矢印 -->
<defs>
<marker id="arrowhead" markerWidth="10" markerHeight="7" refX="0" refY="3.5" orient="auto">
<polygon points="0 0, 10 3.5, 0 7" />
</marker>
</defs>
<line x1="200" y1="60" x2="280" y2="160" stroke="#000" stroke-width="2" marker-end="url(#arrowhead)" />
<text x="220" y="100">コピー1</text>
<line x1="200" y1="110" x2="280" y2="60" stroke="#000" stroke-width="2" marker-end="url(#arrowhead)" />
<text x="220" y="100">コピー2</text>
<line x1="200" y1="160" x2="280" y2="110" stroke="#000" stroke-width="2" marker-end="url(#arrowhead)" />
<text x="220" y="150">コピー3</text>
</svg>
<p>
スタックベースの実装が遅い主な理由：
</p>
<ol>
<li><strong>多数のメモリコピー操作：</strong> データを3回コピーする必要があります。これは特に大きなデータサイズで非常にコストが高くなります。</li>
<li><strong>キャッシュ効率の悪さ：</strong> 大量のメモリアクセスにより、キャッシュミスが頻繁に発生し、性能が低下します。</li>
<li><strong>データサイズに比例する実行時間：</strong> コピー操作の回数がデータサイズに直接比例するため、大きなデータでは著しく遅くなります。</li>
</ol>
<h3>5.2 ヒープベース (swap2) の問題点</h3>
<svg width="600" height="350" xmlns="http://www.w3.org/2000/svg">
<text x="10" y="20" class="title">ヒープベース (swap2) の動作</text>
<!-- データA -->
<rect x="10" y="40" width="180" height="40" fill="#FFB3BA" stroke="black" />
<text x="15" y="65">データA</text>
<!-- データB -->
<rect x="10" y="90" width="180" height="40" fill="#BAFFC9" stroke="black" />
<text x="15" y="115">データB</text>
<!-- 動的割り当てバッファ -->
<rect x="10" y="140" width="180" height="40" fill="#BAE1FF" stroke="black" />
<text x="15" y="165">動的割り当てバッファ</text>
<!-- メモリ割り当て -->
<line x1="200" y1="160" x2="280" y2="160" stroke="#000" stroke-width="2" marker-end="url(#arrowhead)" />
<text x="210" y="155">メモリ割り当て</text>
<!-- コピー操作 -->
<line x1="200" y1="60" x2="280" y2="160" stroke="#000" stroke-width="2" marker-end="url(#arrowhead)" />
<text x="220" y="100">コピー1</text>
<line x1="200" y1="110" x2="280" y2="60" stroke="#000" stroke-width="2" marker-end="url(#arrowhead)" />
<text x="220" y="100">コピー2</text>
<line x1="200" y1="160" x2="280" y2="110" stroke="#000" stroke-width="2" marker-end="url(#arrowhead)" />
<text x="220" y="150">コピー3</text>
<!-- メモリ解放 -->
<line x1="200" y1="190" x2="280" y2="190" stroke="#000" stroke-width="2" marker-end="url(#arrowhead)" />
<text x="210" y="185">メモリ解放</text>
</svg>
<p>
ヒープベースの実装が遅い主な理由：
</p>
<ol>
<li><strong>動的メモリ割り当てのオーバーヘッド：</strong> 一時バッファのための malloc() と free() 呼び出しが必要で、これらの操作は比較的コストが高いです。</li>
<li><strong>多数のメモリコピー操作：</strong> スタックベースと同様に、データを3回コピーする必要があります。</li>
<li><strong>キャッシュ効率の悪さ：</strong><li><strong>キャッシュ効率の悪さ：</strong> 動的に割り当てられたメモリは、連続したメモリ領域にない可能性が高く、キャッシュの効率を下げます。</li>
<li><strong>メモリフラグメンテーション：</strong> 頻繁なメモリの割り当てと解放は、長期的にメモリフラグメンテーションを引き起こす可能性があります。</li>
</ol>
<h3>5.3 Queueベース (swap3) との比較</h3>
<svg width="600" height="250" xmlns="http://www.w3.org/2000/svg">
<text x="10" y="20" class="title">Queueベース (swap3) の動作</text>
<!-- データA -->
<rect x="10" y="40" width="180" height="40" fill="#FFB3BA" stroke="black" />
<text x="15" y="65">データA</text>
<!-- データB -->
<rect x="10" y="90" width="180" height="40" fill="#BAFFC9" stroke="black" />
<text x="15" y="115">データB</text>
<!-- ポインタA -->
<rect x="10" y="140" width="80" height="30" fill="#BAE1FF" stroke="black" />
<text x="15" y="160">ポインタA</text>
<!-- ポインタB -->
<rect x="110" y="140" width="80" height="30" fill="#BAE1FF" stroke="black" />
<text x="115" y="160">ポインタB</text>
<!-- ポインタ交換 -->
<path d="M50,170 Q90,200 130,170" fill="none" stroke="#000" stroke-width="2" marker-end="url(#arrowhead)" />
<text x="70" y="210">ポインタ交換</text>
</svg>
<p>
Queueベースの実装が効率的な理由：
</p>
<ol>
<li><strong>データコピーの回避：</strong> 実際のデータをコピーする代わりに、ポインタのみを交換します。</li>
<li><strong>一定時間操作：</strong> ポインタの交換はデータサイズに関係なく一定時間で完了します。</li>
<li><strong>メモリアクセスの最小化：</strong> ポインタの交換のみなので、大量のメモリアクセスを避けられます。</li>
<li><strong>追加のメモリ割り当て不要：</strong> 一時的なバッファを必要とせず、メモリ管理のオーバーヘッドがありません。</li>
<li><strong>キャッシュ効率：</strong> 少ないメモリアクセスにより、キャッシュの効率的な利用が可能です。</li>
</ol>
<h2>6. 結論</h2>
<p>
スタックベースとヒープベースの実装は、データのコピーに依存しているため、データサイズが大きくなるにつれて性能が著しく低下します。
一方、Queueベースの実装は、データの実体を移動せずにポインタを交換するだけなので、データサイズに関係なく高速に動作します。
これにより、特に大きなデータサイズを扱う際に、Queueベースの実装が他の2つの方法と比較して圧倒的に高速になります。
</p>
<p>
ただし、Queueベースの実装には以下の制限があることに注意が必要です：
</p>
<ul>
<li>データ構造がリスト形式である必要があります。</li>
<li>ポインタを使用するため、データの所有権や生存期間の管理に注意が必要です。</li>
<li>実際のデータの内容ではなく、データへの参照のみが交換されるため、意図しない副作用が生じる可能性があります。</li>
</ul>
<p>
したがって、適切な使用場面を考慮しつつ、Queueベースの実装を活用することで、大幅な性能向上を実現できます。
特に大規模なデータ処理や高頻度の交換操作が必要な場面では、Queueベースの実装が非常に有効です。
</p>
<pre><code class="prettyprint">
#include <sys/types.h>
#include <sys/queue.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
struct listitem {
char *data;
size_t size;
LIST_ENTRY(listitem) entries;
};
LIST_HEAD(listhead, listitem);
void swap1(void *, void *, size_t);
void swap2(void *, void *, size_t);
void swap3(struct listitem *, struct listitem *);
void benchmark12(void (*)(void *, void *, size_t), size_t, int);
void benchmark3(size_t, int);
/*
* Stack-based swap function.
*/
void
swap1(void *a, void *b, size_t size)
{
char temp[size];
char *pa = a, *pb = b;
size_t i;
for (i = 0; i < size; i++) {
temp[i] = pa[i];
pa[i] = pb[i];
pb[i] = temp[i];
}
}
/*
* Heap-based swap function.
*/
void
swap2(void *a, void *b, size_t size)
{
char *temp;
if ((temp = malloc(size)) == NULL)
err(1, NULL);
memcpy(temp, a, size);
memcpy(a, b, size);
memcpy(b, temp, size);
free(temp);
}
/*
* sys/queue.h-based swap function.
*/
void
swap3(struct listitem *a, struct listitem *b)
{
char *temp_data;
size_t temp_size;
temp_data = a->data;
a->data = b->data;
b->data = temp_data;
temp_size = a->size;
a->size = b->size;
b->size = temp_size;
}
/*
* Benchmark function for swap1 and swap2.
*/
void
benchmark12(void (*swap_func)(void *, void *, size_t), size_t size, int iterations)
{
char *a, *b;
clock_t start, end;
double cpu_time_used;
if ((a = malloc(size)) == NULL)
err(1, "Failed to allocate memory for a");
if ((b = malloc(size)) == NULL)
err(1, "Failed to allocate memory for b");
memset(a, 'A', size);
memset(b, 'B', size);
start = clock();
for (int i = 0; i < iterations; i++)
swap_func(a, b, size);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Size: %zu bytes, Iterations: %d, Time: %f seconds\n",
size, iterations, cpu_time_used);
free(a);
free(b);
}
/*
* Benchmark function for swap3.
*/
void
benchmark3(size_t size, int iterations)
{
struct listhead head;
struct listitem *item1, *item2;
clock_t start, end;
double cpu_time_used;
LIST_INIT(&head);
if ((item1 = malloc(sizeof(struct listitem))) == NULL)
err(1, "Failed to allocate memory for item1");
if ((item2 = malloc(sizeof(struct listitem))) == NULL)
err(1, "Failed to allocate memory for item2");
if ((item1->data = malloc(size)) == NULL)
err(1, "Failed to allocate memory for item1->data");
if ((item2->data = malloc(size)) == NULL)
err(1, "Failed to allocate memory for item2->data");
item1->size = item2->size = size;
memset(item1->data, 'A', size);
memset(item2->data, 'B', size);
LIST_INSERT_HEAD(&head, item1, entries);
LIST_INSERT_AFTER(item1, item2, entries);
start = clock();
for (int i = 0; i < iterations; i++)
swap3(item1, item2);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Size: %zu bytes, Iterations: %d, Time: %f seconds\n",
size, iterations, cpu_time_used);
free(item1->data);
free(item2->data);
free(item1);
free(item2);
}
int
main(void)
{
size_t sizes[] = { 8, 64, 512, 4096, 32768 };
int num_sizes = sizeof(sizes) / sizeof(sizes[0]);
int iterations = 1000000;
printf("Testing swap1 (stack-based):\n");
for (int i = 0; i < num_sizes; i++)
benchmark12(swap1, sizes[i], iterations);
printf("\nTesting swap2 (heap-based):\n");
for (int i = 0; i < num_sizes; i++)
benchmark12(swap2, sizes[i], iterations);
printf("\nTesting swap3 (sys/queue.h-based):\n");
for (int i = 0; i < num_sizes; i++)
benchmark3(sizes[i], iterations);
return 0;
}
</code></pre>
</body>
</html>