È possibile restituire stringhe congelate e deduplicate dalla funzione String # split in Ruby?
Se abbiamo una stringa come questa "1,2,3,4,5" e la analizziamo utilizzando una funzione split per ottenere singoli elementi, Ruby alloca un nuovo oggetto stringa per ogni elemento. Se si elabora un file di grandi dimensioni, che ha molti valori duplicati, ad esempio molti 0, la restituzione di stringhe congelate farà risparmiare molto tempo e memoria poiché l'interprete non dovrebbe creare questi nuovi oggetti - potrebbe restituire un riferimento alla stringa congelata - e non sarebbe necessario ripulirla dopo di loro.
Quindi, invece di questo: (ogni oggetto stringa è unico)
2.4.1 :007 > "1,2,3,4,5,6".split(',').map(&:object_id)
=> [70280975267840, 70280975267820, 70280975267800, 70280975267780, 70280975267760, 70280975267740]
2.4.1 :008 > "1,2,3,4,5,6".split(',').map(&:object_id)
=> [70280978671420, 70280978671400, 70280978671380, 70280978671360, 70280978671340, 70280978671320]
Mi piacerebbe vedere questo: (otteniamo gli stessi oggetti stringa nella prima e nella seconda esecuzione)
2.4.1 :007 > "1,2,3,4,5,6".split(',').map(&:object_id)
=> [70280975267840, 70280975267820, 70280975267800, 70280975267780, 70280975267760, 70280975267740]
2.4.1 :008 > "1,2,3,4,5,6".split(',').map(&:object_id)
=> [70280975267840, 70280975267820, 70280975267800, 70280975267780, 70280975267760, 70280975267740]
Ovviamente, questo dovrebbe essere una sorta di meccanismo di opt-in, che ad esempio ti consente di specificare l'elenco di stringhe bloccate che vorresti usare poiché congelare ogni parola in un file sembra chiedere problemi.
Quindi idealmente l'interfaccia sarebbe così:
"1,2,3,4,5,6".split(',', frozen_strings: [-'1', -'2', -'3', -'4', -'5', -'6'])
C'è un modo per farlo in Ruby senza scrivere un'estensione C? Forse usando alcune librerie esterne come i parser CSV?
Risposte
Risposta breve: no
Se il tuo obiettivo è usare stringhe congelate per "risparmiare un sacco di tempo e memoria", allora no, non è possibile farlo split, perché Ruby non è progettato per problemi di gestione della memoria del genere.
Fondamentalmente:
long_string.split(',') # already too late, memory allocations have happened
Ma possibile
La tua unica risorsa in Ruby puro è di non creare le stringhe in primo luogo implementando tu stesso uno split di streaming. Nota che dovrai evitare tutti i normali metodi di iterazione / accesso alle stringhe come each_chare persino []:
str = "1,2,3,4,5"
# both will keep allocating new String objects
str.each_char.map(&:object_id)
(0...str.size).map { |i| str[i].object_id }
Dovrai invece usare qualcosa di simile each_codepoint:
str.each_codepoint { |code| code } # does not keep allocating new objects
# so you could:
str.each_codepoint do |code|
# implement your own parser, taking care to avoid dynamic memory allocations
end
In effetti, se stai veramente lavorando con file di grandi dimensioni, non vorrai nemmeno che l'intera stringa venga caricata in memoria. Ti consigliamo di eseguire lo streaming di letture di file con qualcosa di simileIO.read
E solo per ottenere una chiusura completa, supponendo che tu abbia implementato questo, puoi quindi inserire quella funzione Stringall'interno della tua applicazione per ottenere ciò che volevi in primo luogo.
Prova
str = "1,2,3,4,5"
puts "Run in another shell:"
puts "watch -n 1 'ps ax -o pid,rss | grep -E \"^[[:space:]]*#{$$}\"'"
GC.disable
loop do
# doesn't keep allocating memory
str.each_codepoint { |code| code }
# these keep allocating memory
# str.each_char { |c| c }
# (0...str.size).each { |i| str[i] }
end
Addendum
Estendendosi dal PoC di OP pubblicato in un'altra risposta :
NUMS = [1, 2, 3]
LONG_STR = Array.new(99_999_999) { NUMS.sample.to_s }.join(','); nil
Benchmark.bm(20) do |m|
m.report('my_split') { my_split(LONG_STR) }
m.report('split') { LONG_STR.split(',') }
results = [0, nil, nil, nil, nil, 0, 0, 0]
m.report('tally w/o alloc') do
LONG_STR.each_codepoint do |codepoint|
results[codepoint - 44] += 1
end
end
end
# Run 1 user system total real
# my_split 28.670430 0.541530 29.211960 ( 30.591287)
# split 11.633294 2.578581 14.211875 ( 14.561345)
# tally w/o alloc 12.797672 0.043086 12.840758 ( 12.963547)
# Run 2 user system total real
# my_split 26.526297 0.897670 27.423967 ( 28.084112)
# split 23.000878 3.849396 26.850274 ( 28.269502)
# tally w/o alloc 12.919090 0.035687 12.954777 ( 13.196385)
FYI: il benchmarking di cose in cui un sacco di memoria "thrash" sarà sempre piuttosto non deterministico, poiché non hai il controllo di quando il garbage collector decide di dare il via (e rallenta l'esecuzione).
Oh, e splitpotrebbe essere ancora più veloce con #frozen_string_literal: true, e non ho idea di cosa succederebbe con --jit...
È possibile ottenere una stringa congelata e deduplicata tramite String#-@.
O il mio utilizzo map:
str = '1,1,2,2'
str.split(',').map(&:-@).map(&:object_id)
#=> [70293234167580,
# 70293234167580,
# 70293368908400,
# 70293368908400]
oppure, utilizzando il modulo a blocchi per risparmiare memoria durante l'elaborazione di una stringa enorme: (Ruby 2.6+)
def frozen_split(str, pattern)
return enum_for(__method__, str, pattern) unless block_given?
str.split(pattern) { |x| yield -x }
end
e chiamalo tramite:
frozen_split(str, ',').map(&:object_id)
#=> [70293234167580,
# 70293234167580,
# 70293368908400,
# 70293368908400]
Un semplice to_sympermette anche di riutilizzare gli stessi oggetti. Per esempio:
puts "1,2,3,4,5,6".split(',').map(&:to_sym).map(&:object_id).inspect
puts "1,2,3,4,5,6".split(',').map(&:to_sym).map(&:object_id).inspect
Questo stampa gli stessi ID oggetto:
[70236707757520, 70236707757480, 70236707757440, 70236707757400, 70236707757360, 70236707757320]
[70236707757520, 70236707757480, 70236707757440, 70236707757400, 70236707757360, 70236707757320]
Nota che il to_symmetodo, così come nella risposta di Stefan, dovrebbe far risparmiare memoria (non l'ho misurato), ma la conversione stessa richiede un po 'di tempo.
Quindi entrambi i metodi che riutilizzano gli ID oggetto vengono eseguiti più lentamente rispetto all'impostazione predefinita senza conversione , vedere i risultati del benchmarking di seguito (utilizzando ruby 2.6.6p146 (2020-03-31 revision 67876) [x86_64-darwin18] ). Si noti che qualsiasi codice che utilizzi questi oggetti a valle potrebbe potenzialmente essere eseguito più velocemente, ma non ero sicuro di quale sarebbe stato quel codice nel tuo caso.
Codice di benchmarking:
require 'benchmark'
max_val = 10
[100, 1000, 10_000].each do |num_strings|
puts "###############################"
puts "num_strings=#{num_strings}:"
puts "###############################"
Benchmark.bmbm do |x|
Kernel.srand(1234)
x.report("default") { 10000.times { num_strings.times.map { rand(max_val) }.map(&:to_s).map(&:object_id) } }
x.report("to_sym") { 10000.times { num_strings.times.map { rand(max_val) }.map(&:to_s).map(&:to_sym).map(&:object_id) } }
x.report("-@") { 10000.times { num_strings.times.map { rand(max_val) }.map(&:to_s).map(&:-@).map(&:object_id) } }
end
end
Risultati del benchmarking:
###############################
num_strings=100:
###############################
Rehearsal -------------------------------------------
default 0.367201 0.000213 0.367414 ( 0.367492)
to_sym 0.477524 0.000333 0.477857 ( 0.478012)
-@ 0.489703 0.000129 0.489832 ( 0.489900)
---------------------------------- total: 1.335103sec
user system total real
default 0.369533 0.000336 0.369869 ( 0.370126)
to_sym 0.504686 0.000775 0.505461 ( 0.508025)
-@ 0.497052 0.001251 0.498303 ( 0.499578)
###############################
num_strings=1000:
###############################
Rehearsal -------------------------------------------
default 3.692454 0.005807 3.698261 ( 3.706056)
to_sym 4.628710 0.003317 4.632027 ( 4.633834)
-@ 4.844655 0.004841 4.849496 ( 4.865654)
--------------------------------- total: 13.179784sec
user system total real
default 3.583169 0.002604 3.585773 ( 3.587418)
to_sym 4.709409 0.004160 4.713569 ( 4.717487)
-@ 4.909228 0.010225 4.919453 ( 4.935606)
###############################
num_strings=10000:
###############################
Rehearsal -------------------------------------------
default 37.620197 0.117046 37.737243 ( 37.867851)
to_sym 48.576790 0.156409 48.733199 ( 48.948987)
-@ 49.765026 0.105483 49.870509 ( 49.998702)
-------------------------------- total: 136.340951sec
user system total real
default 36.519696 0.068643 36.588339 ( 36.654737)
to_sym 47.571235 0.157084 47.728319 ( 47.937162)
-@ 49.100705 0.177943 49.278648 ( 49.434869)
NOTA:
Tutte queste operazioni sono piuttosto veloci. Può essere che il collo di bottiglia nel tuo caso non sia nell'allocazione di stringhe, ecc., Ma nell'I / O: lettura / scrittura di file di grandi dimensioni. Quindi potrebbe essere necessario ottimizzare qualcosa di completamente diverso, come evitare di scrivere file di grandi dimensioni utilizzando pipe, ecc.
Grazie alla risposta di Kache ho redatto un PoC che risolve il mio problema. Detto questo, questo codice è molto più lento della splitfunzione originale .
COMMA_CODE_POINT = ','.ord
ONE_CODE_POINT = '1'.ord
TWO_CODE_POINT = '2'.ord
THREE_CODE_POINT = '3'.ord
def my_split(string)
result = []
current_string = []
string.each_codepoint do |codepoint|
if codepoint == COMMA_CODE_POINT
process_string_part(current_string, result)
else
current_string << codepoint
end
end
process_string_part(current_string, result)
result
end
def process_string_part(current_string, result)
if current_string.size == 1
case current_string[0]
when ONE_CODE_POINT
result << -'1'
when TWO_CODE_POINT
result << -'2'
when THREE_CODE_POINT
result << -'3'
else
result << current_string.pack('U*')
end
current_string.clear
elsif current_string.size > 0
result << current_string.pack('U*')
current_string.clear
end
end
Ecco un benchmark di questo codice:
a = "1,2,3,3,2,1,1,2,3,3,2,1,\\N,\\N,asdasda asdasd asdad"
n = 10_000_000
Benchmark.bmbm do |x|
x.report("split") do
n.times do
a.split(',')
end
end
x.report("my_split") do
n.times do
my_split(a)
end
end
end
user system total real
split 21.926568 0.000002 21.926570 ( 21.927100)
my_split 71.138833 0.000000 71.138833 ( 71.140378)
Sono stato in grado di tagliare questo tempo e avvicinarmi molto all'implementazione originale ma con funzionalità molto limitate: la stringa originale poteva contenere solo istanze delle stringhe congelate previste e nient'altro e le stringhe congelate dovevano avere un solo carattere. Immagino che in alcuni casi questo potrebbe essere sufficiente.