Stats

  • Locked Locked
  • Replies 2
  • Subscribers 143
  • Views 15112
  • 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

Most efficient nested data structure?

aakhavan

I'm writing a script to port a design between processes, and I need some kind of data structure that describes how to make the conversion for every primitive instance of the old process. This would include things like the library and cell name of the equivalent instance in the new process, mapping between symbol terminals, mapping between cdf properties, cdf callbacks to run, and any custom functions that need to be called during the conversion process. (I'd include custom functions as strings and use evalstring(), unless there's a better option). This entire structure would be static and loaded from a file. Since there are so many libraries and cells, I need something that can be searched quickly. I realize that the actual conversion process will probably take significantly more time than finding the instructions, but I think the efficiency still matters since it will add up.

There seem to be some tradeoffs between associative tables, disembodied property lists, and defstructs, depending on the number of elements. My understanding is that associative tables are best for long structures, and the defstructs might be better for shorter structures (or maybe DPL's, but the documentation doesn't suggest they're any good). I'm not sure what the tradeoffs between defstructs and associative lists are, but it seems like associative lists are better for things where the keys are unknown, and defstructs for things where the keys are known.

My first thought was:

  • Assoc Table: libraries[]
    • Keys: library names of cells to be converted
    • Values: Assoc Tables cells[]
  • Assoc table: cells[]
    • Keys: cell names of cells to be converted
    • Values: Defstruct cellmap
  • Defstruct: cellmap
    • ?libname - String, library name of new cell
    • ?cellname - String, cell name of new cell
    • ?termmap - Assoc list, keys are old terminal names, values are new terminal names
    • ?propmap - Defstruct, An assoc list similar to termmap except for property names, and a string for callbacks to be executed/custom functions to run on the property value

      Any thoughts?

  • Your proposal seems reasonable. In general I'd say that defstructs are good for the situation where keys are known in advance (although adding an additional ad-hoc key is fairly efficient), and for other indexed lookup, hash tables (assoc tables) are usually a good choice. For small number of keys it doesn't typically matter that much, but for large number of keys it's usually the fastest option.

    That said, for defining mapping from a file, I would often use DPLs and assoc lists because then I can just slurp in the structure directly from a text file using lineread - unless there are lots of keys or those keys are going to change later, this works well; if I really need the performance efficiency (and in general it's best to optimise with real data from the profiler rather than just optimising speculatively - that tends to lead to complicated code which doesn't necessarily address the real bottlenecks in performance) I might store the data in a file using DPLs and assoc lists, but then convert to hash tables/defstructs on read-in (and the other way on write-out).

    DPLs have the benefit of being simple to understand and as with assoc lists they are easy to manipulate using list operators (since they're just lists). DPL operators are destructive (i.e. they modify the list in place) which you need to be aware of - but because both DPLs and assoc lists use sequential searching to find the keys, they don't scale well to large volumes of data (or rather large numbers of keys).

    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.