Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: jseigh Newsgroups: comp.arch Subject: Array vs. Linked List Traversal Date: Thu, 1 Aug 2024 10:55:57 -0400 Organization: A noiseless patient Spider Lines: 9 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Thu, 01 Aug 2024 16:55:56 +0200 (CEST) Injection-Info: dont-email.me; posting-host="6a153a1debd69ad8d8e227a30e586bf0"; logging-data="2340677"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18uUjKMfBnHzdjkPffQk1Si" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:9LHTNUVUBSSOPVMCwVuUV6FJlw8= Content-Language: en-US Bytes: 1335 It's claimed that array traversal is faster than linked list traversal. What would be the reasons for that? Array elements being in cache, assuming the element size is small enough to fit multiple elements in a cache line? No dependent load delay from having to load the linked list next pointer? If that was the case, then moving the load of the next pointer to the beginning of the loop should ameliorate that somewhat. Something else? Joe Seigh