Hi there,
Sorry for the silly question. And I’m wondering why do we need dynamic array in systemverilog, since queue could do everything that dynamic array does. If this is right, what’s the point of having dynamic array, and if not, please correct me. Thanks a lot.
In reply to hazhanken:
Yes, it’s true that a queue gives you all the same functionality as a dynamic array, as well as a fixed sized array. The difference is in the intended use of the array and how the simulator optimizes the data structure that represent the array.
A dynamic array is typically allocated with a size once, and then elements of the array are randomly accessed - similar to a fixed sized array. The elements are allocated contiguously in memory. It’s easy to calculate the address of each element by multiplying the element size by an index value to get an offset from the base address of the array. But if you want to change the size of the array, especially when you want to add more elements, the simulator needs to find an available larger contiguous space for the array and copy the existing elements to that space.
When using a queue, you typically access only the head or tail element, and are repeatedly adding and deleting one element at a time from the head or tail. A queue is implemented as a linked list, which makes head and tail access very simple. But this comes at the expense of taking up more memory for each element, and requires a traversal of elements to get to element in between the head an tail.
Hi dave, i have a question related to above replied answer. we can access a particular element in queue by index. like queue[5]. or insert new element in queue.insert(location, val). so that cannot be the difference between the two.
In reply to to_learn_uvm:
Hi dave, i have a question related to above replied answer. we can access a particular element in queue by index. like queue[5]. or insert new element in queue.insert(location, val). so that cannot be the difference between the two.
What is your question besides repeating the same question and answer above?
I wanted to know the difference between the two.
Hi to_learn_uvm,
I think I understand your question.
You mis-understood Dave’s reply. Dave never said you can’t access non-end entities in a queue.
Like you mentioned, you can access any element in a queue.
Think of it this way: Let’s say to create a dynamic array( let’s say 10 elements), and a queue (for which you add 10 elements). Now, you try to access the 5th element of the dynamic array, as well as the 5th element of the queue.
As Dave mentioned, the tool/simulator, is going to allocate a contiguous section of the memory for the array. Say address 0-9 is allocated for the array. To access the 5th element, the tool/compiler has to just calculate base_address(0) + 5 * (address_size).
For the queue, the simulator can allocate memory anywhere, and just use pointers to get to the next element. For the 10 element queue, each element can have any address in the address space. (Like a linked list). The tool has to now start at the head of this linked-list, and work it’s way to the 5th element, and perform whatever operation you are requesting on the 5th element.
That’s why there is a difference in computation time for the tool when you are using a dynamic array vs queues. As Dave mentions, you can use both, but, if you really care about performance (and other computation aspects of how the tool works), you will have to understand the difference in arrays vs linked-list from a computer science point of view.
PS: And that’s why LinkedList problems like removing a node, adding a node, etc are frequently asked basic questions in any programming interview.
okay, Thanks killsteal and dave. I understand it better.
In reply to dave_59:
In reply to hazhanken:
When using a queue, you typically access only the head or tail element, and are repeatedly adding and deleting one element at a time from the head or tail. A queue is implemented as a linked list, which makes head and tail access very simple. But this comes at the expense of taking up more memory for each element, and requires a traversal of elements to get to element in between the head an tail.
Hi Dave,
I’ve been following you and learn from your answers for years and this is the first time I ask.
My question is why dynamic queue is more memory wise expensive than dynamic or fixed size array?
I did some research but still couldn’t find exact answer, and some of them even shows dynamic queue is more memory efficient than fixed size arrays, because memory is allocated dynamically so there is no need to preserve large amount of contiguous memory.
The reason of me asking this question is, my simulation has been consuming over 50G memory and VCS simprofile indicates it is a UVM sequence causing dynamic memory pool too large. So I suspect it has something to do with dynamic queue.
In reply to Changyu:
Since a queue is implemented as a linked list, when pushing one element onto the list, not only to you have to allocate memory to store the element, you have to allocate memory for a pointer to the next element. And then the OS needs to store a pointer to every chunk of memory it allocates along with the number of bytes allocated. So used on a very conservative estimate on a 64-bit machine, you need a minimum of 25 bytes for every byte pushed onto the queue. A queue of 1000 bytes would take up at least 25000 bytes
A dynamic array needs to store a pointer to the array, and the OS also needs to store a pointer and the number of bytes allocated. A dynamic array of 1000 bytes would take up 1024 bytes.
The number UVM objects you construct is likely a bigger factor than the choice between dynamic arrays and queues. Even the most basic UVM object could take up several hundred bytes. It’s possible you are keeping too many sequence around when they should have been reclaimed. Debugging that will be a tool specific issue.