efficiente aggiungendo in un contenitore a lunghezza variabile di stringhe (Golang)

Question

Il problema:

ho bisogno di applicare più espressioni regolari ad ogni linea di un grande file di log (come diversi GB lunga), si riuniscono le partite non vuoti e metterli tutti in un array (per la serializzazione e inviarlo attraverso la rete).

fette non sono molto aiuto se risposta a this question detiene:

Se la sezione non ha una capacità sufficiente, aggiungono avrà bisogno di allocare nuova memoria e copiare il vecchio corso. Per le sezioni con elementi < 1024, raddoppierà la capacità, per le sezioni con> 1024 elementi lo aumenterà del fattore 1,25.

Poiché ci possono essere letteralmente centinaia di migliaia di corrispondenze regolari, non posso realmente prevedere la lunghezza/capacità di una sezione. Non posso renderlo troppo grande o "solo nel caso in cui bc questo sprecherà memoria (o lo sarà? Se l'allocatore di memoria è abbastanza intelligente da non allocare troppa memoria in cui non è scritto, forse potrei usare un'enorme capacità di slice senza molto danno?).

così sto pensando seguente alternativa:

1. hanno una lista doppiamente linkata di match (http://golang.org/pkg/container/list/)
2. calc la sua lunghezza (? Volontà len() lavoro)
3. preallocare una fetta di questo capacità
4. puntatori di stringa copia a questa fetta

c'è un meno lavoro Il modo in cui raggiungere questo obiettivo in Go (aggiungere alla complessità di appendice ~ O (1))?

(golang novizio qui ovviamente)

Answer 1

s' append()media (ammortizzato) costo è già O (1) perché cresce la matrice di una percentuale ogni volta. Man mano che la matrice diventa più grande, la crescita diventa più economica ma proporzionalmente più rara. Una fetta da 10 milioni di elementi sarà 10 volte più costosa da coltivare rispetto a una porzione da 1 milione di elementi, ma poiché la capacità aggiuntiva che stiamo allocando è proporzionale alla dimensione, sarà anche 10 volte più chiamate append(slice, item) fino alla prossima crescita . Il costo crescente e la frequenza decrescente delle riallocazioni si annullano, lasciando costante il costo medio, cioè O (1).

La stessa idea si applica anche agli array di dimensioni dinamiche di altri linguaggi: l'implementazione di Microsoft std::vector fa aumentare l'array del 50% ogni volta, ad esempio. Ammortizzato O (1) non significa che non si paga nulla per le allocazioni, solo che si continua a pagare con lo stesso tasso medio in cui la matrice diventa più grande.

Sul mio portatile, potrei eseguire un milione di slice = append(slice, someStaticString) s in 77 ms. Una delle ragioni per cui è veloce, che la siritinga ha notato sotto, è che "copiare" la stringa per ingrandire l'array è in realtà solo copiare l'intestazione della stringa (una coppia puntatore/lunghezza), non copiare il contenuto. 100.000 intestazioni di stringhe sono ancora sotto 2MB da copiare, non un grosso problema rispetto alle altre quantità di dati con cui stai lavorando.

container/list si è rivelato ~ 3 volte più lento per me in un microbenchmark; append allegato-list è anche un tempo costante, ovviamente, ma immagino che append abbia una costante più bassa perché di solito è sufficiente scrivere su un paio di parole di memoria e non allocare una voce di elenco, ecc. Il codice di temporizzazione non funzionerà nel Parco giochi ma è possibile copiare questo a livello locale ed eseguirlo per vedere voi stessi: http://play.golang.org/p/uYyMScmOjX

---

ma si sta facendo una domanda più specifica qui circa un applicazione grep -come (e grazie per fare una domanda dettagliata con il contesto). Per questo, la raccomandazione di fondo è che se stai cercando concerti di log, è probabilmente meglio evitare di buffering dell'intero output in RAM.

È possibile scrivere qualcosa per trasmettere i risultati come una singola funzione: logparser.Grep(in io.Reader, out io.Writer, patterns []regexp.Regexp); in alternativa è possibile effettuare out a chan []byte o func(match []byte) (err error) se non si desidera che il codice che invia risultati sia troppo invisibile con il codice grep.

(On []byte vs. string: un []byte sembra fare il lavoro qui ed evita []byte < =>string conversioni quando si fanno di I/O, quindi preferirei che non so quello che tutti voi'. stai facendo, però, e se avete bisogno string va bene.)

Se fai mantenere la lista partita tutta in RAM, essere consapevoli del fatto che mantenere intorno a un riferimento a parte di una grande stringa o di byte fetta mantiene tutta stringa/slice di origine da raccolta di dati inutili. Quindi, se segui questa strada, allora in modo controintuitivo potresti effettivamente volere per copiare le corrispondenze per evitare di conservare tutti i dati del registro di origine nella RAM.

Answer 2

Ho cercato di distillare la tua domanda in un esempio molto semplice.

Poiché ci possono essere "centinaia di migliaia di corrispondenze regolari", ho eseguito una grande allocazione iniziale di 1 M (1024 * 1024) voci per la capacità di sezione matches. Una fetta è un tipo di riferimento. Una struct 'intestazione fetta ha una lunghezza, una capacità e un puntatore per un totale di 24 (3 * 8) byte su un sistema operativo a 64 bit. L'allocazione iniziale per una porzione di voci di 1 M è quindi solo 24 (24 * 1) MB. Se sono presenti più di 1 M, verrà assegnata una nuova sezione con una capacità di 1,25 (1 + 1/4) voci M e le voci esistenti di intestazione della sezione 1 M (24 MB) verranno copiate su di essa.

In breve, è possibile evitare gran parte del sovraccarico di molti append s inizialmente allocando la capacità della sezione. Il problema di memoria più grande sono tutti i dati che vengono salvati e referenziati per ogni corrispondenza. Il problema del tempo di CPU molto più grande è il tempo necessario per eseguire lo regexp.FindAll.

package main 

import (
    "bufio" 
    "fmt" 
    "os" 
    "regexp" 
) 

var searches = []*regexp.Regexp{ 
    regexp.MustCompile("configure"), 
    regexp.MustCompile("unknown"), 
    regexp.MustCompile("PATH"), 
} 

var matches = make([][]byte, 0, 1024*1024) 

func main() { 
    logName := "config.log" 
    log, err := os.Open(logName) 
    if err != nil { 
     fmt.Fprintln(os.Stderr, err) 
     os.Exit(1) 
    } 
    defer log.Close() 
    scanner := bufio.NewScanner(log) 
    for scanner.Scan() { 
     line := scanner.Bytes() 
     for _, s := range searches { 
      for _, m := range s.FindAll(line, -1) { 
       matches = append(matches, append([]byte(nil), m...)) 
      } 
     } 
    } 
    if err := scanner.Err(); err != nil { 
     fmt.Fprintln(os.Stderr, err) 
    } 
    // Output matches 
    fmt.Println(len(matches)) 
    for i, m := range matches { 
     fmt.Println(string(m)) 
     if i >= 16 { 
      break 
     } 
    } 
}