Coda implementata con blocchi

di il
6 risposte

Coda implementata con blocchi

Ciao Forum,

Poiché mi serviva una coda per bufferizzare la seriale, trattandosi di singoli byte e di una quantità di elementi molto variabile (fossi stato certo di un limite superiore ovviamente tutto sarebbe stato banale) ho pensato di implementare la coda come una lista concatenata di blocchi di bytes più dati ausiliari. In pratica la mia struttura dati contiene un array di bytes, i puntatori ai blocchi precedente e successivo (so che si può fare con uno solo ma sono abituato così) e gli indici che delimitano la parte di blocco effettivamente usata. Se devo estrarre il primo elemento lo copio e diminuisco l'indice superiore, se il blocco si svuota viene deallocato, se il primo blocco ha indice zero ne alloco uno nuovo e lo inserisco a inizio lista, e così via.

Il tutto mi funziona apparentemente bene ma non essendo io un ingegnere del software non sono certo di aver creato una serie di test abbastanza esaustiva da farmi escludere bachi. Dato che il mio progetto sta diventando un po' grande ho paura che un baco in parti a basso livello possa passarmi inosservato e farmi cercare a vuoto.

Dunque, la domanda è: implementazioni come quella che ho messo in piedi, si fanno o è una soluzione goffa? E nel caso, che nome hanno così posso cercare in rete? Esistono che voi sappiate librerie con relativa test suite? Magari potrei tentare qualche confronto.

grazie e ciao!

A.

6 Risposte

  • Re: Coda implementata con blocchi

    Sinceramente, per come hai descritto la situazione, mi sembra che tu abbia puntato un po' troppo sul complicato.

    Forse sarebbe bastata una coda circolare semplice (un array) con due indici (p_in e p_out), ma non conoscendo il sistema e i requirements, non so se sia applicabile.
  • Re: Coda implementata con blocchi

    Forse è come dici, probabilmente sono troppo condizionato dall'8088 e sprecare memoria mi dà fastidio; so che oggi non è un problema nemmeno su Raspberry ma è più forte di me. Inoltre, uno dei requisiti che mi ero prefissato è quello di poter conservare tutti i dati della seriale ovviamente ponendo un limite superiore alla memoria usata. In pratica se i dati vengono letti è chiaro che un solo array basta e avanza (parliamo di qualche k al massimo) ma se si accumula qualche decina di mega mi dispiacerebbe allocare tanto spazio per il caso peggiore, spazio che resterebbe quasi sempre inutilizzato.
  • Re: Coda implementata con blocchi

    Beh nel caso, se usi delle liste stai comunque allocando dinamicamente, quindi potresti permetterti di realloc-are il tuo buffer in base alle evenienze.

    Dipende comunque dalla complessità dei dati che ti arrivano: un buon DMA potrebbe tranquillamente gestire quasi interamente la gestione scaricandoti da molto lavoro.

    Comunque il tuo approccio è valido in ogni caso, un pelino poco debuggabile (opinione puramente personale), ma in ogni caso funzionante.
  • Re: Coda implementata con blocchi

    LPs ha scritto:


    Beh nel caso, se usi delle liste stai comunque allocando dinamicamente, quindi potresti permetterti di realloc-are il tuo buffer in base alle evenienze.
    Ci avevo pensato ma non ero certo di saper valutare l'impatto delle operazioni di copiatura. Avevo valutato anche l'idea di una sorta di sistema adattativo che regolasse la dimensione del buffer su qualche retta di regressione ottenuta con la quantità di elementi utilizzati negli ultimi N accessi ma mi sono detto che sono soluzioni sempre "pericolose" perché non danno garanzia sulla velocità media. Ho comunque la curiosità di capire se le operazioni di riallocazione sono sufficientemente "risparmiose" come velocità, il tutto da contrapporre alla maggior complessità della soluzione che ho adottato.
  • Re: Coda implementata con blocchi

    ... se le operazioni di riallocazione sono sufficientemente "risparmiose" come velocità,...
    Non saprei darti una valutazione oggettiva, dipende dalla piattaforma, dalle sue features e anche dalla toolchain/SDK che stai utilizzando.
    Il buon vecchio benchmarking penso sia la via giusta per capirlo.
  • Re: Coda implementata con blocchi

    Visto quanto mi è costata l'implementazione (niente di difficile, solo che controllare tutto porta via tempo) quasi quasi la re-implemento con la riallocazione e metto al lavoro il profiler confrontando le due versioni... credo che MinGW ne abbia uno, è il momento di imparare come usarlo ^_^
Devi accedere o registrarti per scrivere nel forum
6 risposte