C out-of-bound pointer question

Oliver Fromme olli at lurza.secnetix.de
Thu Nov 15 23:56:24 PST 2007


deeptech71 at gmail.com wrote:
 > int x[N];
 > 
 > Values in x[] are (rand()%10)+268435410, aka 268435410..268435419.
 > The algorith counts each individual value.
 > 
 > // v1.0 uses if( x[n] == ___ )'s
 > 
 > // v2.0:
 > int k[268435420] = {0}; // k uses almost 1GB of memory
 > for (n = 0; n < N; n++) {
 >         k[ x[n] ]++;
 > }
 > 
 > // v2.1:
 > int k[10] = {0};
 > int* p = k-268435410;
 > for (n = 0; n < N; n++) {
 >         p[ x[n] ]++;
 > }
 > 
 > The values in x[] are guaranteed, so k[ x[n]-268435410 ] are k[0] to 
 > k[9], but is *((k-268435410)+26843541_) safe? (as long as I do no 
 > dereference such out-of-bound memory region)

In theory, v2.1 should work if the range of the interval
is really guaranteed (you could use assert() to be sure).
The C standard allows such index calculations, which
-- in the end -- is just pointer arithmetics.

However, personally I would use v2.0 because it is easier
to read, and it looks less "dangerous", and it might even
be a little more efficient.

It is true that the k[] array in v2.0 uses 1 GB of mapped
memory, *BUT* it does not use 1 GB of RAM.  It only uses
one page of physical RAM.  Remember that RAM is allocated
dynamically when it is accessed for the first time, so if
you never access k[0..268435409], then no RAM will be
allocated for it.  Of course, you should make sure that
it is a local variable (or a malloc()ed one) that is not
initialized, or otherwise the initialization will cause
RAM to be allocated.  Make sure you initialize only the
indices that you need.

Best regards
   Oliver

-- 
Oliver Fromme, secnetix GmbH & Co. KG, Marktplatz 29, 85567 Grafing b. M.
Handelsregister: Registergericht Muenchen, HRA 74606,  Geschäftsfuehrung:
secnetix Verwaltungsgesellsch. mbH, Handelsregister: Registergericht Mün-
chen, HRB 125758,  Geschäftsführer: Maik Bachmann, Olaf Erb, Ralf Gebhart

FreeBSD-Dienstleistungen, -Produkte und mehr:  http://www.secnetix.de/bsd

"With sufficient thrust, pigs fly just fine.  However, this
is not necessarily a good idea.  It is hard to be sure where
they are going to land, and it could be dangerous sitting
under them as they fly overhead." -- RFC 1925


More information about the freebsd-chat mailing list