Performance and Construction Advice (Priority Queue Lib)

[thick mountain]

Hi all, I've been working on a small crate for the past week learning rust. Was hoping someone might be able to look over it and provide some feedback on any issues or things I could be doing better. I've spent quite a bit of time in flame graph optimizing things but I'm not sure that I'm doing all that I can.

Thanks in advance to anyone willing to provide feedback!

https://github.com/JustinTimperio/rpq

[sacred trellis]

Hello 👋

Ok a few things I can suggest to improve performance would be:

• If you don't have a particular need of hashing or a strong requirement then I would suggest replacing hashmaps with Vec<(datatype, datatype)> this will improve speed by eliminating the hashing overhead on each element insersation and in vector datatype there are also some really efficient functions like swap_remove() which can really improve speed if used in the right way.

• I would look into the build profile flags like lto, strip, codegen-units, etc which you can tweak it for release builds which can give some really good performance.

Also, for a complete guide on different other optimisation techniques you can use I would suggest going through the performance book here 🙂 :

https://nnethercote.github.io/perf-book/introduction.html

I hope this helps 🙂

[granite lynx]

Is this AI-generated? If not, why do you think that Vecs would be better than HashMaps here?

[sacred trellis]

No I wrote it by myself 😅 I think because hashmaps internally use hashing function like they have to hash each key each time on insertion which can have an overhead of O(k + n) time complexity which you know is not great like why have extra time complexity if you don't need it like if you don't have a strong use case for it. I hope you got my point 🙂

[granite lynx]

I have no idea what you're talking about.

[sacred trellis]

Ok I would suggest this post on time complexity of hashing:

https://crypto.stackexchange.com/questions/67448/what-is-the-time-complexity-of-computing-a-cryptographic-hash-function-random-or

I think it will help understand I am saying more clearly.

Also, now after reading this now if you look into how hashmaps work you will see that if you insert any new key value pair what it does is it takes the key and then it uses a hashing function on it and then sorts all the keys based on this newly hashed key now as you can see already the overhead is there like first it needs to hash then it needs to sort and sorting itself can at best be O(n log(n)) now adding both O(k+ n) + O(n log(n)) it just gets worst like why would you want to add such a time complexity on every new key value inserted to your hashmap like it is not very good in performance that's why if you come from c++ there they have talks about data structure where they say try to avoid hashmaps as much as possible use data structures which are memory contingent and also if you don't care about hashing or ddos protection just use vectors they perform way better.

Also, you might argue rust uses swisstable yes I agree it does and it is memory contingent that's why I didn't mention about memory contingency like we have already solved that but what is the hit in performance here is first hashing and then sorting so the overhead internally of a data structure like hashmaps and hashsets are high so that's I suggested going with vectors than with this data structures if you don't have the hard requirements as I mentioned. 😅

I know again this sounds confusing but to understand this I think you might need to study like how internally how each data structure work and you will really understand what I meant. 😅

[granite lynx]

What? A hash table doesn't have to do any O(n log n) sort. And where did this k come from?

I think you're misunderstanding something.

[sacred trellis]

Nah hashmaps has to sort keys internally according to hashes of the key so that's where it comes from. 😅

[granite lynx]

Hashmaps just do an array indexing operation. That doesn't require sorting.

[sacred trellis]

Ok let me check swisstable once...

Ok you are right with swisstable you don't have to. It is just array indexing operation. I am sorry for that misunderstanding but the hashing part is still the overhead why would you want to add that like think about it 😅

[granite lynx]

Because hashmaps are fast for key-value lookups.

[sacred trellis]

Yes true but insertions are slow. And for a queue I don't think hashmaps are great as a whole like inserting each element O(n+k) while inseting an element in vector is just O(1) and O(n) (if you insert from front) quite good in alot of cases while remove is also the same O(1) from back and O(n) from front. And get is O(1) in vector. So you see what I mean that's why even std library we have a vector based deque vecdeque though note it is not contingenious. I hope you got the idea. 😅

[granite lynx]

Inserting into a hashmap is O(1)

[sacred trellis]

Well what about the hashing part it will be an overhead right?

Though don't take this whole discussion as an argument or debate just maybe with our discussion we may get things cleared like I mean all the doubts everything cleared who knows. 😅

[granite lynx]

There is an overhead for hashing, yes. But if you need to search for something corresponding to a key, a HashMap will be better than a Vec, since searching in a Vec is O(n), while searching a HashMap is O(1).

[sacred trellis]

True agreed hmmm... Basically I think it is more like the author has to take the decision according to the need like if we compare both there are both cons and pros so it depends I think. So I think we should leave it on the author to compare and make the best choice. What do you think? 🙂

[short cove]

(amorized yes, but if you insert enough it will have to grow eventually, which is gonna be O(n) as it will have to basically construct a bigger hashmap again from scratch (which is also true for vec, it may need to resize as well)

[deep garnet]

https://github.com/JustinTimperio/rpq/blob/master/src/pq.rs#L200
There are pub fns that are commented as for "internal use only". These should be pub(crate) or module-private if possible, or should at least be #[doc(hidden)]

[iron cairn]

how do you write like an ai

[sacred trellis]

Yes that's what it really depends mostly I think we should best leave it on author to make the best decision like choosing the best data structure depends on what you are trying to solve I feel. 😅

What are your thoughts on this? 🙂

[short cove]

if you do random lookups by key, using a vec of tuples is only gonna be better than a hashmap if there are very few elements

[sacred trellis]

Well, Idk about that tbh like why whatever I write sounds like AI generated though in reality I am typing myself with my thoughts. So no idea why it sounds like that. 😅

[sacred trellis]

Yes but there is a third argument someone can add how would iterators play with each then it should not be O(n) then? 🤔

Though again not trying to argue I am quite open minded of a person would love to hear your thoughts on this because it clarifies alot of things. And also thanks ❤️ for all the explainations so far. 🙂

[thick mountain]

would you mind pointing me in the direction of some docs on this? I have a couple fields that needs to be publicly avail but really shouldn't be used by the user. There are also some fields that are readonly (can be useful for the end client but you can't set them)

[thick mountain]

For my use case Vec is indeed faster than a HashMap given that typically priorities are between the range of 1-1000. I had a friend of my mine look at this and this was his recommendation as well @sacred trellis. I have modified this in recent versions

@here I have resolved a number of the issues in the library and have merged in the RC1 that fixes some bugs and resolves some of the performance and synchronization issues. If anyone would like to take a look feel free

[sacred trellis]

Well after reviewing your PR. I think I would suggest a few things:

• The choice of Vecdeque is good but one thing to note it is not a continginous data structures meaning it will have cache misses alot which can really slow things down if you are reading data alot which is not great. So I would suggest if you can just implement your own dequeue from scratch using purely vectors as they tend to be contigenous and less prone to cache misses. Thus improving performance.

Also, when you implement your own deque structure and if you need to have the need to implement find/search function I think you can take the help of iterators for that like iter + find or iter + filter though I assume they should be O(1) in time complexity seeing the lazy nature of iterators and reading the std library docs though I will still leave the confirmation of whether it is O(1) on Helix(noop_noob) & noratrieb because I could be wrong with this one 😅 .

• I would suggest using iterators more than loops because they have zero cost abstraction and are slightly more performant than loops which becomes more pronounced if you iterate over large number of elements.

Other than that I would suggest setting up clippy lints like:

#![forbid(unsafe_code, clippy::panic)]
#![deny(missing_docs, clippy::missing_docs_in_private_items, clippy::perf)]
#![warn(clippy::cognitive_complexity, rust_2018_idioms)]

Which can really help diagnose your code easily and suggest code suggestion to improve code readability and performance. Though note don't copy and paste the above example blindly I would strongly suggest reading each lint carefully before you do so. 🙂

[granite lynx]

Why on earth would you think that cobbling up a deque from Vecs manually would help?
Why do you think that iterators are more performant?

[sacred trellis]

Well if you read the last paragraph on the vecdequeue docs in the std library it says:

Since VecDeque is a ring buffer, its elements are not necessarily contiguous in memory. If you want to access the elements as a single slice, such as for efficient sorting, you can use make_contiguous. It rotates the VecDeque so that its elements do not wrap, and returns a mutable slice to the now-contiguous element sequence.

Where it says that it is not memory contigent meaning all the elements are not stored in one after the other memory which cause cache misses when you are iterating over this data structure. To understand this I would suggest this video to you:

https://www.youtube.com/watch?v=247cXLkYt2M

And for iterators I think I had seen a benchmark on this and even I have done and it is slightly I mean marginally but quite noticeable when iterating over a large number of elements. 🙂

[rose veldt]

i would like to point out that a VecDeque is continuous in so much as the allocation is as one, so all elements will be local, the only issue would be with a VecDeque that has been grown very large and then most of its elements removed and it happens to cross the max allocation and wraps

[rose veldt]

iterators are very rarely faster than the equivalent loop, and sometimes they are worst, This is very usecase dependent

[sacred trellis]

Well I read this in the std library docs that's why I made the suggestion 😅 :

Since VecDeque is a ring buffer, its elements are not necessarily contiguous in memory. If you want to access the elements as a single slice, such as for efficient sorting, you can use make_contiguous. It rotates the VecDeque so that its elements do not wrap, and returns a mutable slice to the now-contiguous element sequence.

[rose veldt]

yes, this is true but for cache misses it would hardly ever come into play, this is mostly a note about "If you want to access the elements as a single slice"

[halcyon portal]

Ye, a vecdeque at worst means you cache two memory regions that add up to the same size as a single contiguous one

That's not a big deal

Caches dislike your data being scattered in memory. A VecDeque is a bit more scattered than a Vec, but by a tiny margin

[rose veldt]

its not like a linked list that has potentially one page per element

[sacred trellis]

Ok I see cool, there is always something new to learn. I think we should have a talk on this actually like data structures like we have many cpp but none in rust. Like it is a big gap I feel. What do you think? 🙂

[rose veldt]

thats side tracking this thread

[sacred trellis]

Oh yes sorry for that I should have messaged it somewhere else 😅

[iron cairn]

why are you randomly suggesting clippy lints? rather odd clippy lints too?

you have these clippy lints, yet you use Box<dyn Error>

[thick mountain]

My Box<dyn Error> returns seem kind of odd to me. Is the standard that you define a set of errors that can be returned in the lib?

[iron cairn]

yes.

[thick mountain]

k im gonna have to sit down and do that

[iron cairn]

look into thiserror

[short cove]

if youre a library and dont have that many different errors you probably just want to implement your own error types by hand without any other library

[iron cairn]

possiblu

but you can inline the thiserror macro anyways

and sometimes you have a lot of error types

[short cove]

https://sabrinajewson.org/blog/errors i can recommend this blog post as well

[thick mountain]

i think there maybe 10 low level errors that just get passed up to other error returns so prob can hand roll it

[thick mountain]

so is the consensus that VecDeqeue is the correct choice here? The impl i have is about ~15% away in speed from a standard binary heap, and almost all of the overhead is futex syscalls so that data structure is thread safe

[sacred trellis]

Well just as a tip to help them with maintaining code easily. Also, some lints are not bad at all like there is clippy::perf lint for lints specific to performance and idioms one which I think gives suggestions that makes code more readable I feel. Also congnitive complexity one which suggests code changes that reduce mental strain while reading code. 🙂

[iron cairn]

clippy::perf is enabled by default though

i have problems with #![deny] in general, and #![forbid(panic)] is simply silly

[sacred trellis]

I would suggest error_stack if you want to provide errors with more verbosity and information. 🙂

[iron cairn]

dont use error stack

error stack is not for libs

[sacred trellis]

Like it depends on the use case like if you maintain an oss project you don't want to let others introduce panics in places. I hope you got the idea 🙂 . Also, I don't think we should discuss this here like this sounds offtopic so I would suggest having a seperate thread for this one. 🙂

[iron cairn]

just stop them from adding panics that are wrong?

[rose veldt]

A wild panic has appeared!

neon used #![forbid(panic)], it was mildly effective

[iron cairn]

its not like panics are invisible and you cant see them

does clippy::panic look at # Panics too

no its literally just panic!?

[thick mountain]

pardon my ignorance but what exactly is clippy?

[rose veldt]

i don't think so, but also the lint for # Panics would never trigger if you followed clippy::panic

[iron cairn]

https://rust-lang.github.io/rust-clippy/master/index.html clippy

[rose veldt]

its quite a dumb lint (as in it's analysis not its existence)

[sacred trellis]

It is a linter for rust in simple terms. 😅

[thick mountain]

wow this covers a lot

[sacred trellis]

That's why I suggested it. 😅

[sacred trellis]

Well how? they don't mention anything about libs in their docs 😅

[rose veldt]

thiserror or snafu are the big ones

though snafu leaks its involvement sometimes

[sacred trellis]

Well there are so many crates for this. I would again just leave it on the author to choose from. Like they are the one to make the best decision. 🙂

[rose veldt]

error_stack like crates use grouped error types ment for reporting to humans, not for programmatic response to them

most of the time a library should not assume it's errors will just be displayed

[sacred trellis]

Like I mean you could automate stuff with linters and github actions to disallow PRs with such stuff like productivity for the maintainers I feel. What do you think? 🙂

[iron cairn]

i think that panic should be legal

panic is not a mistake

panic is not a problem to be eliminated