Optimization Question

can you post some code?

Also if you are using fstream's read and write functions you should set a chunk size to move each time and not try to move the whole file.

Hope that helps

Here is the class i'm using for the moment.
Place() lets me throw data into the buffer at any point inside the buffer
or right at the end of the buffer.

Del() removes a section of the buffer (beginning or end)

Get() gives me a pointer into the buffer.

The idea is to have a moving window that is of unknown size, but takes up the
least amount of space. ie. I can delete the parts im not using anymore. But it has
to be able to grow, since I am unable to determine what ammount of data processing function needs. (it changes depending on the input data)

problem is that I usually move foward in the buffer, and this means deletes are at the beginnning. This causes a massive slowdown.

Sounds like you need a linked list :)

A std::deque might meet your needs, as it's more efficient for smaller types, and still allows for relatively fast insertion/deletion at the beginning.

Something interesting to look at is some DirectSound code. Streaming music uses this sort of window buffer to do stuff.

Instead of copying the entire thing to a new pointer, you move a pointer within the buffer, writing 'behind' it as it iterates through the buffer, and 'looping' it when it reaches the end. You end up with a fixed buffer which is reused as the information is read/played.

Not sure if this will work for your scenario, but might be something to think about.

This definately sounds like a candidate for using memory-mapped files.
Here's some links I recommend for you:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/fileio/fs/creating_a_file_view.asp
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/fileio/fs/reading_and_writing_from_a_file_view.asp
http://www.catch22.net/tuts/bigmem01.asp

Thanks for the quick responses.
I'll look into the dequeue. Unfortunatly, the memory mapped files will not quite work, neither will the circular buffer.

The main idea I'm working with at the moment is RLE compression.
If you are reading from the file, you decompress each block into the buffer.
Once the buffer reaches an optimal size, you start removing blocks from the beginning of the buffer.

This works great as long as the buffer does not change, but if the buffer changes, then the compressed
version changes, and the buffer tends to grow/shrink in unpredictable ways. Thus the need for the buffer.
Expecially since you can't write to a spot in the file that you haven't read from yet.
So, everything has to be buffered untill there is room in the file to write to.


I understand there is no way this could be as efficient as decompressing the file to a temp
file and modifying that file, compressing and resaving. But it does make it convient for the rest of my code.

[Edited by - KulSeran on September 20, 2005 2:58:18 AM]

I second using std::deque, but using a pooled memory allocator such as the one in the boost library to greatly improve the speed of memory (de)allocations.

EDIT:
On second thoughts, if your compressed files aren't too large you could just keep a copy of the entire *compressed* file in memory as a linked list of run-lengths. Reading a byte is just a matter of scanning along the run-lengths till you find one that contains the requested byte, and writing would just be a matter of splitting the run-lengths (or merging, depending on the data).

The only real speed hit here would be scanning the run-lengths to find the one containing the requested byte(s), but this can easily be improved by keeping a separate list of pointers that point to run-lengths at certain intervals. For example, with an interval of 500 bytes

High level pointers: | 0->A | 1->E | 2->F | 3->H |
Run-lengths: | A=100b | B=200b | C=100b | D=100b | E=500b | F=250b | G=250b | H=100b | I=100b |

If you're look for byte 2030, the pointer you want is floor(1630/500)=3. This points to node H in your linked list, so you scan forward from H until you find the 1630th byte. You only end up checking 2 nodes (H and I) instead of 9 nodes.

In fact, because each run-length is so small (in memory), you may be better off not using a linked list at all and just use a vector. The linked list approach would cause a lot a cache misses, but you'd just have to try both ways to see which was faster.

I am not sure what you mean by 'room in the file' and so on. If you're worried about compression, then you don't even need a buffer; you just track the current value and the run length count.

Is the problem here that you're writing to the original file and need to wait until the read pointer is further ahead than the write pointer? If so, you would make life a lot easier by writing out to a separate file, renaming it at the end. Any intermediate modifications should be possible to do in a fixed-size buffer.

Perhaps a higher level explanation of what you're trying to achieve would help, rather than focusing on the buffer implementation.

It sounded to me like he's trying to modify an RLE compressed file on the fly, so he reads in the relevant parts, uncompresses, modifies, and then writes back out (or something to similar effect).

If so, it's easier to write to a temporary file. The only reason this buffer is changing size is presumably to accommodate the 'lag' between having data to write and having the read pointer past where the data is going to go.

joanusdmentia, that is exactly what im doing.
And kylotan, your right, I am writing to the origional file, and waiting for the read pointer to get ahead of the write pointers.
I also agree that a temp file is the quick solution.

*more explaination*
I'm making a Virtual File System. So far I have implemented the main VFS and file filtering interfaces.
This includes the ability to "plug" in a file system. As long as the file system can distinguish something about a mount string.
ie "c:\temp\" can be accessed through standard file ops.
"c:\temp\arc.zip" would be mounted with a zipfile system.
All the files that get mounted get thrown into one big directory tree, and can be transparently opened.

The buffer is part of the filters for the files (something similar to the flipcode VFS).
The one I have works fine if all I do is reading from the file. It also works fine for read
or write so long as the size of the file doesn't change between the filtered version
and the unfiltered version. But, I thought it would be cool to be able to write
out to a compressed file/archive on the fly.

The day just started, so I haven't had a chance to add in a deque yet, but after playing with it I might give me the speed I want. (if i ever manage to get boost to fully compile under VS2002.net, I will add a poolallocator)

Deque significantly sped up the process.
Though the debug version is still kinda slow, the release version is fast.

Thanks for the help everyone.