Stats

  • Locked Locked
  • Replies 3
  • Subscribers 143
  • Views 13178
  • 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?
Parents
  • 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.....

Reply
  • 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.....

Children
No Data

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.