Мне нужно работать с огромными массивами (более миллиарда элементов), в которых хранятся (неупорядоченные) индексы больших данных (в порядке петабайт и хранятся в матрице SSD).
Размер Массивы не сильно различаются (максимум 10-15%), но для них требуется много операций вставки / удаления.
В некоторых тестах я обнаружил пугающую медлительность, даже для небольших размеров (10 миллионов элементов), которые - изначально - я объясняется неправильной настройкой контроллеров SSD.
При исследовании узкого места я написал программное обеспечение, чтобы определить, в чем проблема.
Я нашел его во вставке (_: at:) и удалить (at:) функций (как для Array , так и для ContiguousArray ).
Чтобы проверить, насколько серьезной была проблема, я написал тест программа, которая проверяет, сколько времени затрачивается - с массивами из 1, 10 и 100 миллионов элементов - для дополнительного количества пар «удаления / вставки» в случайных положениях.
Для возможности воспроизведения Испытание, данные, с которыми нужно работать (и позиции, в которых нужно выполнять удаление и вставку), я получаю из генератора случайных чисел, соответственно посеянного.
import Foundation
import GameplayKit
import CryptoKit
// Parameters - begin -------------------------------------------------------------------------
let ELEMENTS : Int = 1_000_000 // and 10_000_000 and 100_000_000, also used as seed for the random number generator
let ROUND_MAX : Int = (1 << 30) // 1_073_741_824
// Parameters - end -------------------------------------------------------------------------
// Some output formatting aid - begin -------------------------------------------------------------------------
extension String {
func leftPadding (_ length : Int) -> String {
if (length > self.count) {
return (String (repeating : " ", count : (length - self.count)) + self)
}
else {
return (self)
}
}
}
let formatterInt : NumberFormatter = { let numberFormatter : NumberFormatter = NumberFormatter ()
numberFormatter.format = "#,##0"
return (numberFormatter) } ()
let formatterDouble : NumberFormatter = { let numberFormatter : NumberFormatter = NumberFormatter ()
numberFormatter.format = "#,##0.000"
return (numberFormatter) } ()
// Some output formatting aid - end -------------------------------------------------------------------------
// Random generator and time sample initialization - begin -------------------------------------------------------------------------
let randomizer : GKARC4RandomSource = GKARC4RandomSource (seed : String (ELEMENTS).data (using : String.Encoding.utf8)!)
var machTimebaseInfo : mach_timebase_info = mach_timebase_info ()
mach_timebase_info (&(machTimebaseInfo))
var elapsed : UInt64 = 0 // nanoseconds
// Random generator and time sample initialization - end -------------------------------------------------------------------------
// Array initialization and preload - begin -------------------------------------------------------------------------
var array : Array<Int> = Array<Int> ()
array.reserveCapacity (ELEMENTS)
while (array.count < ELEMENTS) {
array.append (randomizer.nextInt ())
}
// Array initialization and preload - end -------------------------------------------------------------------------
// Header output - begin -------------------------------------------------------------------------
print ("\nArray size : \(formatterInt.string (for : ELEMENTS)!) elements\n")
print (" Rounds Elapsed (s) Hash (SHA256)")
// Header output - end -------------------------------------------------------------------------
// Benchmark - begin -------------------------------------------------------------------------
var limit : Int = 1
var counter : Int = 0
repeat {
let start : UInt64 = ((mach_absolute_time () * UInt64 (machTimebaseInfo.numer)) / UInt64 (machTimebaseInfo.denom)) // nanoseconds
// Test section begin -------------------------------------------------------------------------
array.remove (at : randomizer.nextInt (upperBound : ELEMENTS))
array.insert (randomizer.nextInt (), at : randomizer.nextInt (upperBound : ELEMENTS))
// Test section end -------------------------------------------------------------------------
let stop : UInt64 = ((mach_absolute_time () * UInt64 (machTimebaseInfo.numer)) / UInt64 (machTimebaseInfo.denom)) // nanoseconds
elapsed += (stop - start)
counter += 1
if (counter == limit) {
// Hash calculation begin -------------------------------------------------------------------------
var data : Data = Data ()
for element in array {
var item : Int = element
data += Data (bytes : &(item), count : MemoryLayout<Int>.size )
}
// Hash calculation end -------------------------------------------------------------------------
limit <<= 1
print ("\(formatterInt.string (for : counter)!.leftPadding (13)) \(formatterDouble.string (for : (Double (elapsed) / 1_000_000_000.0))!.leftPadding (17)) \(SHA256.hash (data : data).compactMap { String (format : "%02x", $0) }.joined ())")
}
}
while (counter < ROUND_MAX)
// Benchmark - end -------------------------------------------------------------------------
Результаты несколько устрашающие.
Array size : 1,000,000 elements
Rounds Elapsed (s) Hash (SHA256)
1 0.002 138a3face9a95b3a5ba3f089b58c1e2067541e04fd5605841db62998a543ea29
2 0.003 5b295b2183d1412143ea243610b5e8e6eb8f7253e7726aab4e840b64281d675a
4 0.004 bb20a52f6730374c3e37d39b7e8ace180aa46aba3af87a454247c48c9f681e22
8 0.007 d9f512c044e227d5f3df9343f1af7ec6297bd484c7ffb52b14c8acf9b65ba91b
16 0.012 bbb1c4838300b3ae70227b4d85ab5de87f0dc75fd08a5bb48120a3703e391087
32 0.024 f2930403b4ad701d76558eed0ef5a51973f7be7ac641157d7abb0e3c35e75f17
64 0.045 80cb2479d11e2a83dcedca1f59bf11746fe0f513ee5a79cfb1c2e1f1a036d7bb
128 0.092 e3c0495d8b2918bb65d1d33e5170ccc0f056b295ea912c1af46b410fc44e9796
256 0.188 391d7ce33e0fc12f4c14928d55a3e869488a32ad580caf4cfdedbbbe3d7cb44f
512 0.372 41d4c93d04437531ca1463a61608152369f23a2fbdc25780f2975446b51f857f
1,024 0.752 f8287bec62c5fd41cdf3cc820f943688c31afc328aff8edf6a8e2a72060448d4
2,048 1.508 c5de93d9d1c1f449184d46a56796600038a34d39ff97d582b5d6b85a0f5cc970
4,096 3.009 3691fe4a09aba4a192cd7d1b3d9a99541230df1da0efc956a807d2960c129acf
8,192 5.907 fcea1f69f59be2826f9894858d0ba0ca66728ab0d6a6bbc6ea2bc3bd7f884e7a
16,384 11.753 68e40ebd65e232dcfbe8dda1867de2cfaa33cb79a24553dc590b94a6429aa804
32,768 23.332 6168f321dcdc4e7457c383662b33067e5a70dac17a8c0d32903b801570316963
65,536 46.451 e5526d34f40a43151b1848e16b203e35b1ba2c05dc104dc8f7394c26480f91f8
131,072 92.733 cd7e7d27085f74f38800d40a4f6400998c3bf9a01e5dd76da57e6be48e50ceb7
262,144 185.075 0b263633bd06999866994e2670c0094e63514190aaa2aa7437d9274c98d24dc6
524,288 369.582 4d990804a9a39e5a31805c54479b669aec670ba10667c36bf7a5821d211e5e45
1,048,576 739.025 f9c819e38bae6fcccadb19e6d5dc0194b924b4de758446cfb619c6733f027546
2,097,152 1,476.831 3809b4ca104c051fbecdf8adf1c7b85e43f2bdf4a54f3a9fe0f6827fdf829b92
4,194,304 2,951.803 52dcb8edef66f01fcd6a1a399d406bba799b353c8904ffe2206ebed7f366f872
8,388,608 5,904.344 0b1103d71bf007d8e6308b70fa1c2699957ffd8eb2fb68105342fc20c037e37b
16,777,216 *--> Extrapolation: 11,808
33,554,432 *--> Extrapolation: 23,616
67,108,864 *--> Extrapolation: 47,232
134,217,728 *--> Extrapolation: 94,464
268,435,456 *--> Extrapolation: 188,928 (more than two days)
536,870,912 *--> Extrapolation: 377,856
1,073,741,824 *--> Extrapolation: 755,712 (about nine days)
Array size : 10,000,000 elements
Rounds Elapsed (s) Hash (SHA256)
1 0.003 f7c95ec2d5edc4661c3d66f9726282f3befc6596d7fb7c411278cc6bc1b867bf
2 0.014 c7dd7d0a29dd54b716cd7bd50648316c5f9e8ea779dbad439384350eb44b06b2
4 0.037 7848881cca4dd109f7d3c5332c0ef59d22d5d949e4c54c0744f43ec74c18bf27
8 0.059 eeacab6470da127115d1d241f092214bb3ca979ea3c310810c433d64b75ab2c4
16 0.142 6ba190fc0c23e0edca16ddda1c864c09f7780c12a6008b9ef44c29e4793ab538
32 0.266 494025d36bccdc8423a309530ae58e35170cfc5c6dabfc64f8ed17b2c29d4f5d
64 0.570 9a87b4572639785aef28c87f265abb6e8776161cd2220e4feac30f396baa2a16
128 1.196 a56813198d4d1fc9848a02cb6b276bc2159422a0cce6d0d9cebdb11aa587457d
256 2.328 1bb1aca5eb7230dda2c3b949fe916b5382a5f4db3d63dccabb4dce5e2858af94
512 4.612 6b89ccda1d16976e5ef78706b4a0b2f5ceee9f1bd2f4ee239e1fe6ff1ba131e0
1,024 9.455 f62d09dd8ddbebd9052660b33f864e3201a624f8113d8d0bbafc79fe06b28b54
2,048 18.981 00b888459bed2d586ea2aa66095c9543f4383e3be7571146a7534807f832a901
4,096 37.971 a70df557dc5104febab54918c29f2fe32e5b6eb741de54dc9b9c153929f6b710
8,192 75.608 58ae33b7487febd6f806210e191a736415e292111f533b3cb19ece65cd285870
16,384 151.125 d02009e5e858b0026ac3d7cccfc2392f852fb52b38797fb6ad3ff567f55d3344
32,768 302.950 f16d5714bbc29de2423328303542da3276481185750a8e5c2d957c42d0b89ac3
65,536 606.049 51c3f805a8e87fcaf2d394a381c72a821fcc79879e2da85d04f08044331d7276
131,072 1,211.297 39a0c6fde176c1a01cf9ebcd3ae5c18e39aab6a9e0d6e8eca3ffd9df31f390f6
262,144 2,423.513 28f0fae5f453cbe313eddc62d1c010482b1e07693f8a6cc1c33926e95929b98b
524,288 4,851.429 0cc6cd6b129b21b21a281b3178b2f5192fd8556608a569db00361d3f8092dd90
1,048,576 *--> Extrapolation: 9,702
2,097,152 *--> Extrapolation: 19,404
4,194,304 *--> Extrapolation: 38,808
8,388,608 *--> Extrapolation: 77,616
16,777,216 *--> Extrapolation: 155,232 (about two days)
33,554,432 *--> Extrapolation: 310,464
67,108,864 *--> Extrapolation: 620,928 (about one week)
134,217,728 *--> Extrapolation: 1,241,856
268,435,456 *--> Extrapolation: 2,483,712 (about one month)
536,870,912 *--> Extrapolation: 4,967,424
1,073,741,824 *--> Extrapolation: 9,934,848 (about four months)
Array size : 100,000,000 elements
Rounds Elapsed (s) Hash (SHA256)
1 0.092 151e39fe153c331587677dadcbbe7d70e2b8d71c3a6691e3b89ac5e718287a47
2 0.253 87505250156e85dbb89f8728d8ed2ea1c6bd64e27ab544b6d402e38ef1f710e4
4 0.336 f4c544f12fb55d36dae203b20023fdb3114cbb9625657b8a09258d89959b97b2
8 0.744 bc9e082a6c1cc773e5783d2a9703860d06be68fbae6d8f76ddd5d0eaf48ba84b
16 1.473 1028a636e69bf2a920b81fb632e1b40c816c967938683dea9a3b5f02b418ec5a
32 2.998 43aa5a981a15905229c2ca43cf0b6176364c160b5394c9a767f6e17a35a0fca4
64 5.843 bed576d60984b6dbecac4852f897e90bc87d9ed595bd4a818367ae473ae5330a
128 11.688 fd77e56b314dfb3baa0b6af269580d908d675a7c6a287b327de0529908ae0198
256 23.995 bc2dc20d22edc68b5fb149d941328428bec00e94d1f3b60733a24f72fdcef1a9
512 47.643 be1f23a307fdfa55648481f9932821339fd291d9ab6c6f5ff92641e341a27259
1,024 95.298 973023792197d8f127a10fdad4f4fd9e833d8f859f215db9167be7cba348590d
2,048 190.741 766e6970f7e6e454465faafbce570166454463878dae58861164ff9d32257c40
4,096 381.089 7b96bc8e43e7f69ce69bed2f881381ba2bd7dc1e37ba32e8e15a224eebe636f4
8,192 767.318 f25ece1854b8941a6c34de3ea6eb931bb7cf8644ee0c672d31eb8fd0d8e0ac4c
16,384 1,541.048 0a7681ebf2d82c312c56e3d3e4cd4be61e6080799b9b8cca037e5daecc2df4d8
32,768 3,097.719 315404e3bbd39a90fa0473fa126e8d30352566f81490704cccd0682ef08c7ffe
65,536 *--> Extrapolation: 6,196
131,072 *--> Extrapolation: 12,392
262,144 *--> Extrapolation: 24,784
524,288 *--> Extrapolation: 49,568
1,048,576 *--> Extrapolation: 99,136
2,097,152 *--> Extrapolation: 198,272 (more than two days)
4,194,304 *--> Extrapolation: 396,544
8,388,608 *--> Extrapolation: 793,088 (more than one week)
16,777,216 *--> Extrapolation: 1,586,176
33,554,432 *--> Extrapolation: 3,172,352 (more than a month)
67,108,864 *--> Extrapolation: 6,344,704
134,217,728 *--> Extrapolation: 12,689,408
268,435,456 *--> Extrapolation: 25,378,816 (about ten months)
536,870,912 *--> Extrapolation: 50,757,632
1,073,741,824 *--> Extrapolation: 101,515,264 (more than three years)
Теперь у меня есть два вопроса:
1) Есть ли способ ускорить вставку / удаление элементов - в случайных позициях (не добавляя и не добавляя) - в массивах размера I нужно?
2) Если да, то как?
Спасибо в avance.