I know you said "call them numbers", but if they really are bytes of disk I/O data, the one-byte value range restriction does leave open the possibility of a very small index -- you could mark the first occurrence of each value in each of the buffers during the sequential scans.

Other metadata could be computed as well, if they will be revisited frequently, like run-length of a particular value.

During the merge operation, you might be able to speed up merge point decisions into what's left of the etherical 10% side buffer based on knowing where to go to get the next chunk of data that needs resequencing.

In fact, a run-length table in lieu of actual data might buy you the space you need for a one-pass optimization. Forget saving index offset. Save the value and the number of them. (WARNING: Corner case where lots of length < sizeof(integer) runs causes the working buffer to actually be larger than the source buffers should be considered.). Then just overwrite the buffer with the resulting data.

This would, of course, be an application-specific solution and not a general case proof for all airless merges, but sometimes that's the call the Engineer has to make.

Okay, I'm done spamming you for the moment and heading home. This one sounds basic but fun; I'll be following this thread closely.

I think this has triggered a workable idea.

Given a 2GB buffer of (minimum) 8-byte records = 268,435,456 records; using 1-bit per record requires 32MB. Well within my 10%.

So, what can I record with 1-bit?

My first though is that I can record whether this record is contiguous with the preceding one. Ie. Is is equal to it; or exactly one greater. In effect, contiguous runs of 1-bits become chunks of the buffer(s) that can be translocated to their final position en-masse.

And (I think) by processing down those bitmaps in parallel (though not lock-step), and knowing the first value in each of the two buffers, it gives me a a straight forward map of how things have to be moved into their final positions.

Does that convert the original O(N²) process into an O(2(or 3?)N) process?

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Not sure -- it's been a long time since I've had anything detailed enough to warrant computational analysis of the execution cost (I miss the old days when I worked on fun stuff).

A side trip, though, if a full run length index might have had value (does not look like it here), here's a Perlized representation. Some of the code is sloppy, but I didn't go home like I said I would so I optimized Wife-Deprivation Units at the cost of Code-I-Could-Be-Proud-Of Units.

Okay, so here's a proof-of-concept. The assumption is that a Run-Length table will consume notably less space than the original data, such as might be true in a disk I/O operation. This is not a universally-applicable assumption but may yield thoughts toward optimization in your specific case.

Read more... (3 kB)

Results on my test run:

D:\PerlMonks>perl merge1.pl
Buffers:
     [AAAAAABBCCCDDDDEEEEE]
     [AAAABBBBBBCCCCCDDDDD]
Buffers:
     [AAAAAAAAAABBBBBBBBCC]
     [CCCCCCDDDDDDDDDEEEEE]

D:\PerlMonks>
[download]

The more I've thought about this, the more I doubt the first pass is really going to buy much at all that'll make your merge more efficient.

In the long run, you still have to do the same comparisons and the same moves. In terms of performance, it doesn't matter much which loop they're in. My original thought above, if it's feasible at all, only really adds overhead in almost every case.

The only little chance of saving anything, I think, is if you have a chunk of data at the beginning or end of the combined buffer that doesn't have to move. You might be able to identify that on your first past and shorten your second pass to the data in between.

That's all I got.

The only little chance of saving anything, I think, is if you have a chunk of data at the beginning or end of the combined buffer that doesn't have to move.

That's exactly what the pre-scan is doing. "Topping and tailing" the two buffers for bits that either don't need to move, or only need to be block-moved rather than merged:

                  |---|
               ---|   |                 ___
             ---      |           ___---
         ---          |     ___---
      ---             |__---
   ---|               |
---   |               |
[download]

Don't read too much into the ascii art, but there are obviously two chunks, the left and right ends of the left buffer, that can be either left where they are or just block-moved into place, respectively.

There are 5 other possibilities:

1. 1 requires no further processing: all of the left buffer is less than all of the right buffer.

   (Full scan required.)

2. 1 requires a single block swap; all of the left buffer is greater than all of the right buffer.

   (Full scan required.

3. 4 (including the above) that either leave in place or block-move two smaller chunks and need to recurse on the other two.

   (Partial scan if left in place or full if moved.)

What I was looking for was something discoverable or doable during that first scan, that abetted the next stage.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

I'm coming to the same conclusion. Inevitably, all my creativity winds up solving the "how to conserve space" and to a lesser degree the "how to minimize data moves" issues -- and none of my thinking in those areas is yielding a first-pass-scan benefit.

This is maddeningly entertaining because I can't count the number of times in my career I could optimize the inner algorithm if only I had the privilege of a pre-processing linear scan, which was too costly to be worth implementing.

Here, I have the exact opposite problem -- I am going to get a pre-processing linear scan, and I can't make use of it to optimize the inner process.

Somewhere, some deity of software development is having a huge guffaw at my expense.

:-)