Stats

  • Locked Locked
  • Replies 3
  • Subscribers 143
  • Views 13177
  • Members are here 0
This discussion has been locked.
You can no longer post new replies to this discussion. If you have a question you can start a new discussion

How NOT to slurp a file into SKILL....

tweeks 
;; Return the contents of FILE as a string... extremely slowly.
(defun BcmFileSlurpSlowly (file "t")
 (let (port line (lines ""))
   (unless (setq port (infile file))
      (error "Can't open %s" file))
    (while (gets line port)
      (setq lines (strcat lines line)))
    (close port)
    lines))

;; Return the contents of FILE as a string less slowly.
(defun BcmFileSlurpQuick (file "t")
  (let (port line lines)
    (unless (setq port (infile file))
      (error "Can't open %s" file))
    (while (gets line port)
      (push line lines))
    (close port)
    (buildString (reverse lines) "")))


> (sh "ypcat passwd > /tmp/passwd")
> (sh "wc -l /tmp/passwd")
39076 /tmp/passwd
t
> measureTime (BcmFileSlurpSlowly "/tmp/passwd")
(207.8354 1.708741 209.6785 0)


Three and a half minutes for a 39 kiloLine file?! :O



> measureTime (BcmFileSlurpQuick "/tmp/passwd")
(0.06999 0.001 0.07150483 0)

That's better. :)

Questions:

  1. Why is strcat so much slower than push + buildString + reverse?
  2. Why doesn't allocate('string 39076) help make the strcat() method faster?
  3. Could this be done even more quickly than BcmFileSlurpQuick()? What is the fastest known way to slurp a file in SKILL?
  • Andrew Beckett

    Tom,

    I don't think it's anything to do with garbage collection or pre-allocation of memory (BTW, allocate() is private, so you shouldn't use it, as the consequences of using it aren't documented. needNCells is documented, but that has different behaviour). 

    For me it took about 25 seconds (for a 41k passwd file). Not great, but not as slow as you. When I ran through the profiler, it took 46 seconds, 10 of which were gc. If I used allocate() it got much worse - probably because it potentially had more pre-allocated memory to garbage collect? (the gc went up to 100 seconds with a allocate of 10000 - actually the number of pages is limited to 10000 even if you ask for more)

    I think the most likely explanation is because strings are not mutable in SKILL. So each time you do a strcat it is having to create a brand new string, copying the previous contents. So it's going to have to copy the entire string so far into the new location - and that gets bigger and bigger on each successive copy and is going to be O(N^2) where N is the number of strings. I'd say the buildString approach is going to be pretty quick - sure, you're allocating a list but this is fairly efficient.

    I can't think of a quicker way in the absence of mutable strings.

    If you have control over the format of the file and can make it SKILL-like, then lineread is quite an effective way of reading it in. But then it's not a single string...

    Regards,

    Andrew.

  • tweeks

    First, sorry for the slow response: I was on vacation, then I got sick, then my Cadence.com account decided to stop working.... 

    Second, thank you very much Andrew for the thoughtful and detailed reply.

    Andrew Beckett said:

    I think the most likely explanation is because strings are not mutable in SKILL. So each time you do a strcat it is having to create a brand new string, copying the previous contents. So it's going to have to copy the entire string so far into the new location - and that gets bigger and bigger on each successive copy and is going to be O(N^2) where N is the number of strings. I'd say the buildString approach is going to be pretty quick - sure, you're allocating a list but this is fairly efficient.

    Makes sense.

     

    Andrew Beckett said:

    I can't think of a quicker way in the absence of mutable strings.

    I'm surprised you didn't suggest tconc to get rid of the reverse(). :)

    Andrew Beckett said:

    If you have control over the format of the file and can make it SKILL-like, then lineread is quite an effective way of reading it in. But then it's not a single string...

    You made me think of creating a file that contains a giant double-quoted string, and then calling lineread() on it....  However, I believe there is a documented limit of 8k for strings read by read() or lineread().

    In retrospect, returning a giant string is generally less useful than a list of lines anyway.....

  • Andrew Beckett

    tweeks said:

    I'm surprised you didn't suggest tconc to get rid of the reverse(). :)

    I'm surprised you didn't use it in your example either! To be honest, that would be a relatively small refinement to what you did which I doubt would make a significant difference to the performance.

    Regards,

    Andrew. 

Community Guidelines

The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.