On Aug 4, 2011, at 5:26 PM, Michael Lachmann wrote:
> Hi,
>
> I was trying to have R read files faster with readChar(). That was before I
noticed that readChar() is not that bad! In any case, below I suggest a few
simple changes that will make readChar slightly faster.
>
> I followed readChar(useBytes=T), and tried to identify all O(N) operations,
where N is the size of the file. The assumption is that for LARGE files we want
to avoid any O(N) operations, and any O(N) memory allocations.
>
I'm not sure it's really worth bothering with such optimizations, on my
machine I get
> system.time(readChar("large.file",1e8,T))
user system elapsed
0.295 0.048 0.343
so that is a fraction of a second for 100MB of data. Besides, why in the world
would you want to use character vectors to store bytes? It's much more
efficient to work with raw vectors instead...
AFAICS the only lesson from the list below is that we could add in an internal
function for safe_mkCharLenCE that doesn't check for NULs. But that seems a
little contrived for a very special case. Everything else is either increasing
complexity at the cost of safety or could lead to internal inconsistencies
(hashing is mandatory, otherwise you can't compare CHARSXPs).
BTW: your code doesn't do what you think it does - you'll force a pretty
ugly buffer overflow - perfect illustration why optimization should be done only
if really needed, otherwise you are just likely to introduce bugs...
Cheers,
Simon
> Here they are:
>
> 1. In readFixedString in envir.c, an N sized vector is
> allocated, and memset to 0. O(N)
>
> 2. The file is read into the buffer with con->read O(N) (but this
probably can't be dropped)
>
> 3. mkChar is called, which calls mkCharLenCE(name, strlen(name),
CE_NATIVE);
> strlen is O(N)
>
> 4. In mkCharLenCE, a loop along the string looks for 0s to tell if the
string includes NULs (notice that because strlen was called before, that
can't really happen) O(N)
>
> 5. A hashcode is computed for the string to see if it is already in memory.
That is an O(N) operation.
>
> 6. A Charsxp of size N is allocated
>
> 7. The data is copied to the Charsxp - O(N).
>
> So, as far as I could tell, in addition to the reading operation, 5 O(N)
operations are done, and double the memory of what is needed is allocated.
>
> A couple of these operations are easy to drop:
>
> 1. One could only zero the memory beyond what was read, in case not N chars
were read.
>
> 2. We know the length of the string, so we can call mkCharLenCE directly
from readFixedString with the right length.
>
> Others could maybe be dropped.
>
> 3. Does one really need to look for 0s?
> In readFixedString there is a comment:
> /* String may contain nuls which we now (R >= 2.8.0) assume to be
> padding and ignore silently */
> 4. If a file was just read, is it likely that it is in the hash? Is it
worth paying the time for those people who read in the same file twice?
>
> Finally about the allocation.
>
> Could the Charsxp be allocated to begin with, and the data read straight
into it?
> Then we'd save one extra allocation, and a memcpy. For that one would
need something like mkEmptyCharLen.
>
> One could also allocate a slighly bigger memory region, and then pass that
so that instead of allocating it a new the old pointer is used (?).
>
> In any case, here is an updated readFixedString(), which would drop 2 O(N)
operations.
>
> ---
> static SEXP
> readFixedString(Rconnection con, int len, int useBytes)
> {
> SEXP ans;
> char *buf;
> int m;
> const void *vmax = vmaxget();
>
> if(utf8locale && !useBytes) {
> int i, clen;
> char *p, *q;
>
> p = buf = (char *) R_alloc(MB_CUR_MAX*len+1, sizeof(char));
> memset(buf, 0, MB_CUR_MAX*len+1);
> for(i = 0; i < len; i++) {
> q = p;
> m = con->read(p, sizeof(char), 1, con);
> if(!m) { if(i == 0) return R_NilValue; else break;}
> clen = utf8clen(*p++);
> if(clen > 1) {
> m = con->read(p, sizeof(char), clen - 1, con);
> if(m < clen - 1) error(_("invalid UTF-8 input in
readChar()"));
> p += clen - 1;
> /* NB: this only checks validity of multi-byte characters */
> if((int)mbrtowc(NULL, q, clen, NULL) < 0)
> error(_("invalid UTF-8 input in readChar()"));
> }
> }
> } else {
> buf = (char *) R_alloc(len+1, sizeof(char));
> //memset() was here
> m = con->read(buf, sizeof(char), len, con);
> if(m < len )
> memset(buf, m+1, len+1); // changed
> if(len && !m) return R_NilValue;
> }
> /* String may contain nuls which we now (R >= 2.8.0) assume to be
> padding and ignore silently */
> ans = mkCharLenCE(buf, len, CE_NATIVE); // changed (one could also use no.
read bytes as size)
> vmaxset(vmax);
> return ans;
> }
> --
>
> The other changes are also not that hard - I'd do them if people think
such changes should be included....
>
>
> Thanks for listening,
>
> Michael Lachmann
>
> ______________________________________________
> R-devel at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-devel
>
>