Persistent stack implementation

jeteve has asked for the wisdom of the Perl Monks concerning the following question:

Hello fellow perl lovers,

I'm searching for a LIFO implementation but can't find any suitable.

I tried BerkerleyDB::Recno (+ cursors), but the performances are far less than the BerkeleyDB::Queue. So I'm looking for an implementation that should be:

Persistent (disk based will do)
Concurrent access safe
Fast

I know this sounds a bit demanding, but I can't believe such an important data structure implementation doesn't exists. Thanks for any help !

-- Nice photos of naked perl sources here !

Comment on Persistent stack implementation

Replies are listed 'Best First'.
Re: Persistent stack implementation (a file) by tye (Sage) on Nov 09, 2007 at 19:13 UTC
A single, simple file and a lock seems all you need. You push by lock,append,unlock. You pop by lock,seek,read,truncate,unlock. You don't say what types of values you want to store. But the worst case would be to write after each item (in a fixed-width format) the size of the previous item. - tye	[reply]
Re: Persistent stack implementation by dragonchild (Archbishop) on Nov 09, 2007 at 18:18 UTC
It's not optimized as of yet, but you could use DBM::Deep as an array. It's persistent and concurrent-access safe. It even has ACId transactions. If performance becomes a major concern, I can do some optimization on shift and unshift. My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]
Re: Persistent stack implementation by perrin (Chancellor) on Nov 09, 2007 at 18:32 UTC
You tried BDB::Queue and it doesn't work for you? Is it not FIFO? Or just too undocumented? There's not much that can compare in speed to BerkeleyDB. You could do something with a local copy of MySQL. That's about as fast it gets after BDB if you want a real database. You could also try hacking something on top of Cache::FastMmap, but it's a cache, not a database, and not built to be ACID.	[reply]
Re: Persistent stack implementation by gam3 (Curate) on Nov 10, 2007 at 00:59 UTC
Did you try Stack::persistent? -- gam3 A picture is worth a thousand words, but takes 200K.	[reply]
Re: Persistent stack implementation by jbert (Priest) on Nov 09, 2007 at 18:38 UTC
I guess your persistency criterion rules out a unix fifo (`mkfifo foo`)? Another option would perhaps be system V message queues (see `perldoc -f msgsnd` and IPC::MSg. But people often think these suck.	[reply] [d/l] [select]
Re^2: Persistent stack implementation (s/L/F/) by tye (Sage) on Nov 09, 2007 at 20:19 UTC
I guess your persistency criterion rules out a unix fifo (`mkfifo foo`)? That and the fact that FIFO is a pipe not a stack (FILO). :) Another option would perhaps be system V message queues Queues are usually FIFOs as well. I can almost hear it: "FILO?! D'Oh!" - tye	[reply]
Re^3: Persistent stack implementation (s/L/F/) by jbert (Priest) on Nov 09, 2007 at 21:37 UTC
Very prescient. D'oh! In which case, you just need to reverse your puts and gets. I'm sure it will all work out all right in the end. More seriously, the suggestion of using a file (with locking and fixed length records) is a good one. That should be fairly straightforward.	[reply]
Re: Persistent stack implementation by jdporter (Paladin) on Nov 10, 2007 at 17:38 UTC
Tie::File is essentially an array persisted to disk. It does have some (limited) support for concurrent access. A word spoken in Mind will reach its own level, in the objective world, by its own weight	[reply]