Marek080:
One post stated that EEPROM access works on pages and a page is 32 bytes (I think it was an external EEPROM).
That is not correct for the internal EEPROM. Access is byte-wise.
I read in the ATmega328 specs that there are 256 pages each 4 bytes large.
Wouldn't happen to have been in the section about external programming?
Somehow all the gathered information does not match the measured access times.
The access time for one byte is exactly what is described in the datasheet: load two registers (1 cycle each), fetch the data (1 cycle), 2 cycle pause for a grand total of 5 cycles (0.3125 us). The majority of what your sketch is measuring is the overhead of preparing the call, shuffling data to where it belongs, and looping.
Write results are 103464, 106796, 103516 and 106852. A single byte takes approx. 3.5ms - somebody posted 3.5 to 8ms as normal.
8ms is not normal and would very likely indicate a serious problem with the processor. 3.4ms is the erase + write time; nicely close to the value you measured.
This brings me to the point where I should only write data that changed
A very good idea.
and preventing blocking calls to let other tasks work while writing. Is there something I missed?
You could take a stab at making writes interrupt driven. If your application will be reading from sections that could have pending writes you will have to include a cache.
Edit: no eeprom_update_byte() in Arduino 1.0 (see avr-libc: <avr/eeprom.h>: EEPROM handling). Seems we are using an older version.
Yup. There are instructions for upgrading to a newer version in the forum or you could just steal eeprom_update_byte from a newer version of Libc.