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