Sliding window

[filia&sofia]

Let me rephrase my question that hasn't been answered properly. I want
to read a file into n-bit chunks of data _extremely fast_, process the
chunks and finally write them back into a different file. The problem
is that usually people suggest algorithms that are slow.

I'm thinking that the possible algorithm should first read the file
into a buffer (in computer memory), which is large w.r.t. length of
the individiual chunk of bits. Secondly, one should try to avoid slow
operations such as "for". Maybe operations like memmove or memcopy
would do the trick, but how?

So, basically, one could think that the algorithm is like a window
that goes through a file sequentially showing at a time only the n-bit
chunk. There isn't a trivial solution, because computers process bytes
instead of bits and the algorithm has to be state-of-art.

Any suggestions? Thank you.

 

[Bartc]

Let me rephrase my question that hasn't been answered properly. I want
to read a file into n-bit chunks of data _extremely fast_, process the
chunks and finally write them back into a different file. The problem
is that usually people suggest algorithms that are slow.

I'm thinking that the possible algorithm should first read the file
into a buffer (in computer memory), which is large w.r.t. length of
the individiual chunk of bits. Secondly, one should try to avoid slow
operations such as "for". Maybe operations like memmove or memcopy
would do the trick, but how?

So, basically, one could think that the algorithm is like a window
that goes through a file sequentially showing at a time only the n-bit
chunk. There isn't a trivial solution, because computers process bytes
instead of bits and the algorithm has to be state-of-art.

Any suggestions? Thank you.

How big are typical chunks? A typical file?

When read into memory, do you want them byte-aligned? (If not, just reading
the entire file into memory will also read all the chunks into memory; then
you could process them in-situ, perhaps using a special pointer format that
includes bitfield info)

memmove and similar functions are all byte-aligned. If the chunks are big,
you can use memmove etc on the main portion, but I guess you may want the
chunk bit-shifted (so it starts on the beginning of the first byte, but may
still have unused bits in the last byte)

Will the alignment on output be the same as in the input?

I don't have any actual answers, but sometimes providing more details such
as these can elicit better help.

 

[Richard]

Let me rephrase my question that hasn't been answered properly. I want
to read a file into n-bit chunks of data _extremely fast_, process the
chunks and finally write them back into a different file. The problem
is that usually people suggest algorithms that are slow.

I'm thinking that the possible algorithm should first read the file
into a buffer (in computer memory), which is large w.r.t. length of
the individiual chunk of bits. Secondly, one should try to avoid slow
operations such as "for". Maybe operations like memmove or memcopy
would do the trick, but how?

So, basically, one could think that the algorithm is like a window
that goes through a file sequentially showing at a time only the n-bit
chunk. There isn't a trivial solution, because computers process bytes
instead of bits and the algorithm has to be state-of-art.

Any suggestions? Thank you.

Yes. Buy a good book on programming and programming C in particular.

This is generally considered the bible:

http://www.amazon.com/Programming-Language-Prentice-Hall-Software/dp/0131103628

 

[filia&sofia]

Nice to have help.

How big are typical chunks? A typical file?

Actually, there are no typical chunks or typical file. The length of
the chunks are dynamically assigned and typical file is any file e.g.
game setup file or DVD movie.

When read into memory, do you want them byte-aligned? (If not, just reading
the entire file into memory will also read all the chunks into memory; then
you could process them in-situ, perhaps using a special pointer format that
includes bitfield info)

memmove and similar functions are all byte-aligned. If the chunks are big,
you can use memmove etc on the main portion, but I guess you may want the
chunk bit-shifted (so it starts on the beginning of the first byte, but may
still have unused bits in the last byte)

I want only the bits that exist in the file originally. The length of
the chunks should be ceil(n/8) bytes. Also, the bits that do not hold
any information are located at the "Most Significant Bit" end. In
short, the read information (in bits) is represented in bytes.

For example, if the file has: "0110 0100 1111 1101 0011 0101 0101 1100
0000" and n=9.
Then, 1st chunk is (without padding) "0110 0100 1". 2nd is "111 1101
00". 3rd is "11 0101 010" and 4th is "1 1100 0000".
Now, we need two bytes to represent nine bits. We pad all the chunks
with zeroes, e.g. 1st becomes "0000000 011001001" etc.

Will the alignment on output be the same as in the input?

The output file is same as the input file: the algorithm has to remove
padded zeroes and join chunks in the way that preserves information in
overlapping bytes. At this point, the algorithm should produce
identical files in a extremely fast manner.

Hopefully, this additional information helps.

 

[filia&sofia]

Yes. Buy a good book on programming and programming C in particular.

This is generally considered the bible:

http://www.amazon.com/Programming-Language-Prentice-Hall-Software/dp/...

I've already read this book. It's a good book to learn basics. But for
example it doesn't consider at all the complexity of the algorithms or
optimization of the code. But thanks for the effort.

 

[Bartc]

I want only the bits that exist in the file originally. The length of
the chunks should be ceil(n/8) bytes. Also, the bits that do not hold
any information are located at the "Most Significant Bit" end. In
short, the read information (in bits) is represented in bytes.

For example, if the file has: "0110 0100 1111 1101 0011 0101 0101 1100
0000" and n=9.
Then, 1st chunk is (without padding) "0110 0100 1". 2nd is "111 1101
00". 3rd is "11 0101 010" and 4th is "1 1100 0000".
Now, we need two bytes to represent nine bits. We pad all the chunks
with zeroes, e.g. 1st becomes "0000000 011001001" etc.


The output file is same as the input file: the algorithm has to remove
padded zeroes and join chunks in the way that preserves information in
overlapping bytes. At this point, the algorithm should produce
identical files in a extremely fast manner.

Hopefully, this additional information helps.

Actually, it's made things more confusing! I've looked at your earlier post
and from that it seemed you need some sort of combined move+bitshift.

I assume your N in that post (buffer byte size) can be bigger than a machine
word? And the M bits at a time you're taking from that buffer can also be
bigger than a machine word?

Best to post some C code here, so that assuming it works as you want, you
might be able to get help with optimising.

 

[Ben Bacarisse]

Nice to have help.

I though you got a pretty good answer last time. At least say why
is was unsuitable or what is wrong with what you've already tried. It
may be that you are aiming for something that is impossible.

Actually, there are no typical chunks or typical file. The length of
the chunks are dynamically assigned and typical file is any file e.g.
game setup file or DVD movie.

Does that really mean that the chunk-size can change at any time and
that you can put no upper bound on it? If so, I think you may be
short on options. (By "at any time" I mean that it varies from chuck
to chuck as the file is processed.)

How fast can you read the data? Do a little benchmark to read the
data source using a reasonable buffer -- you'll get an answer like
"56x10^6 bytes/sec with a 16Kb buffer". Then say what bit rate you
hope to get as output if that is possible -- "I'm hoping to output
48x10^6 9-bit chunks per second". That will let anyone considering a
solution know how mach slack there is.

Finally, I'd want to know how portable you need the solution to be.
Must you use C standard I/O? Can you assume a particular byte-order
within larger types? Can you use 64-bit or even extended integer
types? I doubt I'll have any useful answers for you, but I'd want to
know these things in order to have a go.

 

[Anonymous]

Any suggestions? Thank you.

Google "Ring Buffer"

 

[filia&sofia]

I though you got a pretty good answer last time. At least say why
is was unsuitable or what is wrong with what you've already tried. It
may be that you are aiming for something that is impossible.

Sorry, I don't recall answers from you. What was your solution again?

Does that really mean that the chunk-size can change at any time and
that you can put no upper bound on it? If so, I think you may be
short on options. (By "at any time" I mean that it varies from chuck
to chuck as the file is processed.)

Again, my mistake. When the program starts, the length of the chunk is
assigned. But after the start, the length doesn't change.

How fast can you read the data? Do a little benchmark to read the
data source using a reasonable buffer -- you'll get an answer like
"56x10^6 bytes/sec with a 16Kb buffer". Then say what bit rate you
hope to get as output if that is possible -- "I'm hoping to output
48x10^6 9-bit chunks per second". That will let anyone considering a
solution know how mach slack there is.

As fast as possible. But the read/write rates depend on technical
properties, don't they?

Finally, I'd want to know how portable you need the solution to be.
Must you use C standard I/O? Can you assume a particular byte-order
within larger types? Can you use 64-bit or even extended integer
types? I doubt I'll have any useful answers for you, but I'd want to
know these things in order to have a go.

Nice question. At this point I'm just trying to get my first version
of the program done. I thought that I could do it using C. This is
partially because I need to use extended integer types and arbitrary-
precision arithmetic, and there are few possible C libraries to do
those things. Portability is not an issue, yet.

 

[Walter Roberson]

Nice to have help.

I though you got a pretty good answer last time. At least say why
is was unsuitable or what is wrong with what you've already tried. It
may be that you are aiming for something that is impossible.
[...]

He says that he wants to avoid using "for" because it's
a "slow operation." Go figure.

Probably needs something non-portable like "scatter-gather" asynch I/O
that DMA's into buffers that the O/S "flips" directly into user space
instead of -copying- them into user space.

But what do I know? That sort of the thing has been in use in HPC
for over a decade, and the OP requires that the approach be
"state of the art". I dunno what that means. Directly programming
SATA controllers and reserving transfer-slots on PCI-X ?? Is it
"state of the art" to use RAID-6 to stripe the data on multiple discs
to increase the I/O rate? Using the fastest drives available
is an idea as old as computing, so that isn't "state of the art" so I
guess there's no point in the OP thinking about that...

 

[filia&sofia]

He says that he wants to avoid using "for" because it's
a "slow operation." Go figure.

Nested k-level for-loops have time complexity of O(n^k).

O(n) algorithms' time complexity increases linearly.

 

[Bartc]

Nested k-level for-loops have time complexity of O(n^k).
O(n) algorithms' time complexity increases linearly.

I don't fully understand the O() notation, but I have a feeling the above is
nonsense.

Anyway a for-loop isn't that slow, there's a small overhead per iteration,
which may be insignificant depending on what's in the loop. And there are
ways of minimising that overhead.

But I doubt what you need will involve deeply nested for-loops.

Post some code here (using any method including for-loops) and we'll see if
it needs to be improved.

 

[filia&sofia]

I found some relevant information from encode.ru forums:

"about i/o - there are few std ideas that you may use

1) don't use fgetc/fputc. make your own buffer instead:

inline putc(c)
{
*curptr++ = c;
if curptr >= bufend
-- write
}

2. if you really need fast i/o - use 3 threads - for read, compress
and write. read/write data in large chunks. use circular buffers.
preread large enough amount of data (for example, for quad what
compress data in 16mb blocks, you should use 4*16mb preread buffers
and at least 2*16mb output buffers)"

Also comment for looking up "ring buffer" was good.

 

[Walter Roberson]

He says that he wants to avoid using "for" because it's
a "slow operation." Go figure.

[/QUOTE]

Nested k-level for-loops have time complexity of O(n^k).

Only if the limit on each is O(n). If the limit on all except one is
O(1) then the overall result is O(n).

For example,

for (i=0;i<n;i++)
for (j=0;j<BUFSIZ;j++)
/* some code here */

The inner code is O(n), not O(n^2).

O(n) algorithms' time complexity increases linearly.

You haven't given us enough information about the processing for
us to know whether an O(n) algorithm is even possible in these
circumstances. It looked to me, based upon what you wrote, that the
minimum was -probably- O(n log n), but it was hard to tell.

 

[Willem]

Bartc wrote:
)
) )>
)>> He says that he wants to avoid using "for" because it's
)>> a "slow operation." Go figure.
)
)> Nested k-level for-loops have time complexity of O(n^k).
)> O(n) algorithms' time complexity increases linearly.
)
) I don't fully understand the O() notation, but I have a feeling the above is
) nonsense.

The first line (nested k-level for loops ...) is utter nonsense.

The second line is reasonably sensible if you implicitly read 'with the
size of the input', but even then it's not 100% accurate.
However, it is totally unrelated to the current topic under discussion.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[filia&sofia]

Let's put it this way, I'm trying to read n-bit numbers from a file.
I'm looking for "fast" ways to do this.

P.S. What's fast? I consider data compression programs such as THOR
and QuickLZ fast in compressing data.

 

[Richard]

Let's put it this way, I'm trying to read n-bit numbers from a file.
I'm looking for "fast" ways to do this.

P.S. What's fast? I consider data compression programs such as THOR
and QuickLZ fast in compressing data.

Since when did compression come into it?

You are providing no information. "Fast" is a relative thing. If you
have ideas about "fast" then you must have ideas about what isn't fast.

"Run fast" is something just about every program should aim to do - not
thinking about that has led to the incredible bloatware which infests
platforms today and ensures that PCs which are 1000 times faster than 20
years ago open a Word Processor in the same time as opposed to in a
blink of an eye.

Most C programmers use C because they have an eye on efficiency in terms
of CPU and memory usage IMO.

 

[filia&sofia]

Since when did compression come into it?

It didn't.

You are providing no information. "Fast" is a relative thing. If you
have ideas about "fast" then you must have ideas about what isn't fast.

It seems that everyone here needs strict conditions to be able to say
anything. "Fast" is relative thing. "Compression" was an analogy.

"Run fast" is something just about every program should aim to do - not
thinking about that has led to the incredible bloatware which infests
platforms today and ensures that PCs which are 1000 times faster than 20
years ago open a Word Processor in the same time as opposed to in a
blink of an eye.

And this is relevant?

Most C programmers use C because they have an eye on efficiency in terms
of CPU and memory usage IMO.

Perhaps.

 

[Richard]

It didn't.


It seems that everyone here needs strict conditions to be able to say
anything. "Fast" is relative thing. "Compression" was an analogy.

Compressions was nothing to do with it. Are you seriously trying to
explain your use of "fast" by mentioning that compressions may be or
may not be fast depending on the algorithm?

And this is relevant?
Yes.


Perhaps.

And still you do nothing to provide information needed to answer your
question other than your pie in the sky "it must be fast".

I was trying to say that this isn't specific enough because "fast"
should be an aim for most program IMO. And "fast" can be specified in
many ways -fast to start up, fast to read a file, total time, use lest
system or cache memory etc etc etc.

It seems to me you're just looking for someone to write your program. I
hope someone does for you, but until then why not post your attempt and
then other people can comment on structure and choice of algorithms to
hopefully optimise it yet further.

 

[Ben Bacarisse]

Sorry, I don't recall answers from you. What was your solution
again?

I did not give one. Eric Sossman gave you the "standard" way to do
this (sorry Eric, no offence) and I saw no point in my saying more
without knowing what was wrong with his suggestion.

Again, my mistake. When the program starts, the length of the chunk is
assigned. But after the start, the length doesn't change.

OK. Any bounds on it at all?

As fast as possible. But the read/write rates depend on technical
properties, don't they?

I think you've missed my point. Give the technical people here
something to get their teeth into. "As fast as possible" will make
(most) people move on to the next posting. With no bounds on the
chuck size there will be no "as fast as possible" -- or at least not
just one, there will be a whole set of them -- and I doubt anyone can
say exactly what they all are. The best for 65-bit chucks is likely
to be very different to the best for 7-bit ones. It is not hard to
code, so you could say what you have and why it is not good enough.

Nice question. At this point I'm just trying to get my first version
of the program done. I thought that I could do it using C. This is
partially because I need to use extended integer types and arbitrary-
precision arithmetic, and there are few possible C libraries to do
those things. Portability is not an issue, yet.

That is rather unfortunate since "as fast as possible" will probably
mean you need lots of systems specific tricks which are not topical
here.