C'è anche un debugger molto comodo perché hacker / cracker / reverser-oriented, solo per Windows, ma adesso non ricordo il nome. Open source.
tornando a quanto dicevo, anche OpenBSD !CitazioneOpenBSD took an interesting approach in the 3.8 release:During the development cycle of the 3.8 release, changes were made to the malloc memory management functions. In traditional Unix operating systems, malloc allocates more memory by extending the Unix data segment, a practice that has made it difficult to implement strong protection against security problems. The malloc implementation now in OpenBSD makes use of the mmap system call, which was modified so that it returns random memory addresses and ensures that different areas are not mapped next to each other. In addition, allocation of small blocks in shared areas are now randomized and the free function was changed to return memory to the kernel immediately rather than leaving it mapped into the process. A number of additional, optional checks were also added to aid in development. These features make program bugs easier to detect and harder to exploit: instead of memory being corrupted or an invalid access being ignored, they often result in a segmentation fault and abortion of the process. This has brought to light several issues with software running on OpenBSD 3.8, particularly with programs reading beyond the start or end of a buffer, a type of bug that would previously not be detected directly but can now cause an error. These abilities took more than three years to implement without considerable performance loss and are similar in goals to that of the Electric Fence malloc debugging library by Bruce Perens.
OpenBSD took an interesting approach in the 3.8 release:During the development cycle of the 3.8 release, changes were made to the malloc memory management functions. In traditional Unix operating systems, malloc allocates more memory by extending the Unix data segment, a practice that has made it difficult to implement strong protection against security problems. The malloc implementation now in OpenBSD makes use of the mmap system call, which was modified so that it returns random memory addresses and ensures that different areas are not mapped next to each other. In addition, allocation of small blocks in shared areas are now randomized and the free function was changed to return memory to the kernel immediately rather than leaving it mapped into the process. A number of additional, optional checks were also added to aid in development. These features make program bugs easier to detect and harder to exploit: instead of memory being corrupted or an invalid access being ignored, they often result in a segmentation fault and abortion of the process. This has brought to light several issues with software running on OpenBSD 3.8, particularly with programs reading beyond the start or end of a buffer, a type of bug that would previously not be detected directly but can now cause an error. These abilities took more than three years to implement without considerable performance loss and are similar in goals to that of the Electric Fence malloc debugging library by Bruce Perens.
Citazione da: cdimauro - 05 Dicembre 2014, 07:06:38Aggiungi -> prima o poi lo spazio finisce e devi effettuare il resize (quindi, di nuovo, allocare e deallocare).C'è una grossa differenza però, se io ho una struttura dati, posso deallocare solo alcune parti (e non ci sono operazioni di copia, etc). Nel riallocare un blocco intero di memoria, per esempio com'è comune nei buffer anche due mega o più, non è detto che l'allocator possa garantirti un'allocazione del genere (ovvero in una zona "continua" se c'è molta frammentazione)
Aggiungi -> prima o poi lo spazio finisce e devi effettuare il resize (quindi, di nuovo, allocare e deallocare).
Citazione da: cdimauro - 05 Dicembre 2014, 07:06:38Utilizzare strutture dinamiche, come liste concatenate (FIFO), richiede più memoria ed è decisamente più lento rispetto a un array con accesso diretto alle sue entry.[...]Però immagina il tipo PyList, un altro di quelli che viene spesso utilizzato (oppure StringIO, che viene molto usato per generare pagine web o, in generale, buffer di dati che vengono costruiti): cosa utilizzeresti per implementarlo in maniera efficiente a run-time?A parte il fatto che per evitare continui realloc dovresti partire con un buffer molto grande e non credo che questo consumi meno memoria rispetto ad una struttura dati.
Utilizzare strutture dinamiche, come liste concatenate (FIFO), richiede più memoria ed è decisamente più lento rispetto a un array con accesso diretto alle sue entry.[...]Però immagina il tipo PyList, un altro di quelli che viene spesso utilizzato (oppure StringIO, che viene molto usato per generare pagine web o, in generale, buffer di dati che vengono costruiti): cosa utilizzeresti per implementarlo in maniera efficiente a run-time?
/* This over-allocates proportional to the list size, making room * for additional growth. The over-allocation is mild, but is * enough to give linear-time amortized behavior over a long * sequence of appends() in the presence of a poorly-performing * system realloc(). * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */
Non conosco in dettaglio StringIO, ma se non utilizzano una lista che per il sequential access è davvero molto efficiente, sicuramente stanno adottando un strategia di ottimizzazione sbagliata.
typedef struct { PyObject_HEAD char *buf; Py_ssize_t pos, string_size;} IOobject;
Attualmente la linear list è la struttura dati più veloce per il sequential access ed anche per il direct access (se si hanno poche entry, ma vedi dopo).
Nel dictnotes.txt trovi che una possibile ottimizzazione per poche entry è il linear search, soprattutto se viene fatta in una zona continua di memoria. Mentre hashi la chiave, probabilmente il linear search ha già finito :-)
Per l'ottimizzazione del direct access, le tree sono abbastanza efficienti, ma in alcune librerie ho visto che molti per semplificare utilizzano sempre liste con skip-list (per saltare direttamente in alcune parti di memoria) ed offrono performance superiori alle tree (in realtà "dipende", ma il discorso è un po' lungo).
Ovviamente non sono paragonabili a delle zone di memoria allocate, ma come detto prima non è sempre possibile garantire una riallocazione più grande (ed il fatto che oggi il computer più scarso ha 4gb di ram, non è un motivo per adottare tale soluzione).
E questa non è una cosa scoperta di recente, gli anni 80 sono stati gli anni del "linear search rediscovered". A tal proposito vorrei incollare una parte del libro The School of Niklaus Wirth, The Art of the Simplicity, un libro che da ex-Pascalliano ti consiglio cdimauro :-)
books_to_read.append("The School of Niklaus Wirth, The Art of the Simplicity")
Citazione I still vividly remember the day that Wirthdecided to replace the elegant data structure used in the compiler’s symbol tablehandler by a mundane linear list. In the original compiler, the objects in the symboltable had been sorted in a tree data structure (in identifier lexical order) for fastaccess, with a separate linear list representing their declaration order. One day Wirthdecided that there really weren’t enough objects in a typical scope to make thesorted tree cost-effective. All of us Ph.D. students were horrified: it had taken timeto implement the sorted tree, the solution was elegant, and it worked well – so whywould one want to throw it away and replace it by something simpler, and evenworse, something as prosaic as a linear list? But of course, Wirth was right, and thesimplified compiler was both smaller and faster than its predecessor.
I still vividly remember the day that Wirthdecided to replace the elegant data structure used in the compiler’s symbol tablehandler by a mundane linear list. In the original compiler, the objects in the symboltable had been sorted in a tree data structure (in identifier lexical order) for fastaccess, with a separate linear list representing their declaration order. One day Wirthdecided that there really weren’t enough objects in a typical scope to make thesorted tree cost-effective. All of us Ph.D. students were horrified: it had taken timeto implement the sorted tree, the solution was elegant, and it worked well – so whywould one want to throw it away and replace it by something simpler, and evenworse, something as prosaic as a linear list? But of course, Wirth was right, and thesimplified compiler was both smaller and faster than its predecessor.
All'inizio ero molto scettico, soprattutto dopo aver passato anni ad usare hash table e poi tree (che mi piacciono da morire) per ottimizzare il lookup o l'accesso,
ho dovuto fare vari benchmark e poi in alcuni programmi sostituire strutture dati incasinate con le liste per convincermi che dipende che dati vai a trattare, sono dannatamente veloci
stavo pensando, secondo me i 64bit di indirizzamento non mitigano troppo il problema anche per il fatto che poi la MMU si vede tipicamente block_size + larghi e quindi non vorrei che finisse per i discorsi analoghi che si fanno sui filesystem dove per il block_allocator, se non si prendono utili provvedimenti, dopo un po' non riesce piu' a garantire in modo alcuno continuità di blocco. Per il filesystem non e' critico, semplicemente le prestazioni calano (e la frammentazione aumenta), per un memory allocator invece potrebbe essere meno piacevole, e chiaro cmq che dipende da come lavora la MMU e da quanta memoria usano le tabelle. Meno memoria usa per le tabelle e + ram deve gestire la MMU + grossi si fanno i block_size.
Lo swap (su Windows 8.1) l'ho disattivato. Con 16GB è del tutto inutile.
beati voi che potete