memory reading vs. writing

I'm making a lookup table (1 x 256 array of unsigned chars) to record all unique pixel values found in an image. I initialize the array to all 0s; then I want to write 1 to each element where the array index equals a pixel value in the image.

I can simply scan the image and write 1 to the array every time, resulting in many unnecessary writes since if, for example, the value 155 appears 15,000 times in the image I'm writing 1 to table[155] 15,000 times.

Or, I can put the assignment in an if statement and write a 1 only if that table entry is 0, so when 155 is read from the image, I test table[155], write 1 to table[155] only 1 time, but subsequently test it in the if statement 14,999 additional times.

Which takes less time?

It would depend on the hardware, but a 256 byte array can easily fit into a cache, so I'd have to guess that reading would be faster. I'm not sure what effect the addition of a branch would have though

Profile it and find out.

Is your "memory" flash memory with disproportionately large write times compared to read times (for example), or is it your regular DRAM?

Or how good is your processor at branch prediction, which your alternate code will have an awful lot of?

the if statement still needs to index that element in the array, so it seems to me what you're really asking is if unsigned char::++ or unsigned char::= is faster than if(unsigned char)

should be easy enough to test.

set up two loops that do each of the two operations a few thousand times and compare the times required to complete each of the loops.

personally i'd just go for the former method you mentioned, as that is a straightforward lead in to making a histogram, which will likely be useful in the future.

Actually I have several platforms in mind -- all pretty low-end when it comes to power...

a robot with a mips7000 processor and sdram
a robot with a hitachi h8s processor and flash memory
various pc's/laptops with celeron and several-years-old pentium or athlon processors (none 64 bit).

Sounds like maybe I'll have to test each one. I was just wondering to what extent I might generalize. For example, Salem's comment about flash memory suggests that the "if" approach is likely to be better for the hitachi.

I don't know anything about the branch prediction capabilities of these processors.

Certainly with such a range, I doubt a single answer would be the best in all cases.

But before you catch a really severe case of "premature optimisation disease", how have you determined that this is a real bottleneck?

Quote:

---

Originally Posted by Salem

But before you catch a really severe case of "premature optimisation disease", how have you determined that this is a real bottleneck?

---

The short answer is that I haven't. But I'm writing image-processing code for computer vision applications that will run on "underpowered" platforms, so as I proceed I'm trying to keep optimization in mind. This particular instance involves a table that in some apps may have to be rebuilt (with new values) 15 - 30 times per second. I haven't even determined that it's possible on this hardware, but I want to be sure that I don't sabotage myself with sloppy code from the outset.

In addition, this question is general enough that it can arise in any number of applications so it seemed worth thinking about even if it turns out not to be an issue immediately.

sounds more and more like a histogram is going to be of use at some point.

Quote:

---

Originally Posted by m37h0d

sounds more and more like a histogram is going to be of use at some point.

---

Not necessarily, and the original question is also valid in apps that have nothing to do with histograms so it seems worth considering by itself.

> This particular instance involves a table that in some apps may have to be rebuilt (with new values) 15 - 30 times per second
Example:
-----
Lets say QVGA (320x240=76800) x 15 = 1152000 bytes of pixel data / second.
If you have a 50Mhz machine, you've got 50 ticks to process an image, and leave no capacity for anything else. So I'm guessing no more than 20 would be good.
-----


Whatever the results are for your situation, it might give you some idea as to whether
- no problem
- could be a problem that needs special attention
- it's hopeless, we need hand crafted assembler to come even close to this!

Oh, I've been digging in the H8 manual.
> I test table[155], write 1 to table[155] only 1 time, but subsequently test it in the if statement 14,999 additional times.
If you don't care which bit is set, then the "TAS" instruction seems to be the fastest way of achieving this. Now all you need do is figure out which code causes the compiler to generate that code.

Never say hopeless. Worst case, I have to process fewer images & discard the rest.

Quote:

---

Originally Posted by Salem

>Oh, I've been digging in the H8 manual....Now all you need do is figure out which code causes the compiler to generate that code.

---

Here is a clear example of "premature optimisation disease". :D

I hadn't planned to get to that level of detail at this stage. But it's a useful indication of what may be involved in answering the original question. Your interest is appreciated.

btw, not to keep plugging this forum, but the DSP guys at kvr.org focus a lot on optimization. they might be useful also.

It sounds like you're doing some palette reduction, but since you've only told us about one little loop we can't see the bigger picture and as such can't point out an algorithm that would give a speed boost of some order of magnitude. We're instead forced to micro-analyse one little loop in the hopes of boosting the performance of just that loop by perhaps 10%.
Please tell us the BIG picture!

To answer the original question: In most processors, read and write operations take the same amount of time, so to read first, then maybe update will be slower.

Writing to flash memory is not just a write, you'd have to have a small function that writes several commands to the flash and then writes the actual content, and finally polls to see that the data has been written correctly. This is not something you should do inside a tight picture analyzing loop - that would not work well at all - moreover, erasing and rewriting flash memory is not an operation that you should be doing frequently, as all flash memory has a limit to how many times it can be erased - about 1 million. But in this case, timing of the writes is in the microseconds range (v.s. tens of nanoseconds for RAM), so it would certainly be completely unsuitable to do this to flash memory.

I'd say that all systems that use flash memory also have RAM - it may be fairly small, but there will be some. If nothing else, the call-stack needs to be in RAM, as you can't possibly implement a stack in flash.

--
Mats

Quote:

---

Originally Posted by Salem

But before you catch a really severe case of "premature optimisation disease", how have you determined that this is a real bottleneck?

---

He has to choose one of the two implementation strategies anyway.

I'd say go with write-only, since it's simpler code.