search

contour-terminal / contour

Modern C++ Terminal Emulator
http://contour-terminal.org/
Apache License 2.0
2.43k stars 106 forks source link

generate hash keys using AES-NI #328

Open christianparpart opened 3 years ago

christianparpart commented 3 years ago

Use AES-NI for accelerated cache key generation. Fallback to FNV on non supporting platforms

Maybe have this as a small library the org namespace.

See https://gist.github.com/vurtun/e658197f9ee8f956ef82b98e457c115d

Affirmative: https://github.com/B-Con/crypto-algorithms in case I cannot find a good ARM AES implementation.

Make use it it for glyph run cashing

data-man commented 3 years ago

Why not xxhash3 https://github.com/Cyan4973/xxHash? Or any other fast hasher from https://github.com/rurban/smhasher.

christianparpart commented 3 years ago

xxhash3

Hey, many thanks for all those informational links. I wasn't looking at alternatives yet until now. ;) I had a look at both links, and xxHash seems certainly promising. OTOH at first I didn't even consider adding a 3rdparty dependency for that because you can implement AES-NI based hashing in just ~6 lines of simple code, that would not justify a complete oversized dependency. But I do not know what is the best (in terms of performance and stability), so relying on others prior research definitely would help in the decision making.

I did not decide yet how exactly to go with. But we definitely have to improve performance on hashing because upon every frame render the whole grid (partitioned into glyph runs) will be generating a hash for every partition (this may very well be up to a couple of thousands). Along with that, the way we cache the glyph runs would need to be optimized to. But one step at a time. i.e. first release 0.2.0. :)

WSLUser commented 3 years ago

I'd hold off on any optimizations or third party deps until WIndows Terminal makes their hashing story better. They've already got a good hashing mechanism in place but it is one of the pain points in a perf trace so they'd like to do a refactor to optimize it further . (They recently did something to help with hashing but it's based on a design architecture that they want to improve so they can boost perf more in many ways including hashing).

jerch commented 3 years ago

@christianparpart Imho murmur3A is also worth a look in terms of speed for a fallback.

@WSLUser What does this have to do with windows terminal?

christianparpart commented 3 years ago

@christianparpart Imho murmur3A is also worth a look in terms of speed for a fallback.

Thx @jerch. I mean, the title says AES-NI, but in the end I'm open to whatever turns out to be the best(fastest) in our use-case. I am currently using FNV.

jerch commented 3 years ago

Well it is more meant as a fallback thingy. I have no numbers for AES-NI, but I am pretty sure you cannot beat native circuits with any software hash trickery.

Edit: Well, actually a GPU based simplistic software hash might be even better, if you can use it to your advantage (result needed on GPU only for glyph tiles and such). But for glyph caching you might not even need a hash with a big period, since the "glyph space" is quite small in terms of typical hash periods. There you might get away with a very simple PRNG approach, and check for collisions in the glyph space prehand. Would give you a hash by only a few shift/xor operations, if carefully chosen.

WSLUser commented 3 years ago

What does this have to do with windows terminal?

They share some commonalities in that they are both C++ terminals. So anything Contour does should be similar to what Windows Terminal does. I do want to say maybe some optimizations would be ok but try to keep it easy to break away from if a better one comes along. You could still use something similar to what WT has now and it would be better than nothing. Just bear in mind the perf costs associate with hashing.

uspasojevic96 commented 3 years ago

What does this have to do with windows terminal?

They share some commonalities in that they are both C++ terminals. So anything Contour does should be similar to what Windows Terminal does. I do want to say maybe some optimizations would be ok but try to keep it easy to break away from if a better one comes along. You could still use something similar to what WT has now and it would be better than nothing. Just bear in mind the perf costs associate with hashing.

This doesn't make any sense, why should Contour do anything that WT is doing? Just because they are VTE?

jerch commented 3 years ago

@WSLUser Haha, well thats like telling someone to stop tinkering, or an engineer to stop engineering, because some other more famous party might come up with a better solution one day (they dont have it yet).

You know what - there is a (still very big) institution, that tried to keep ppl imprisoned in that mindset for almost 2000 ys. And honestly, we would still sit in the trees, if ppl would not feel the urge to solve things their very own way. It is the driving force behind cultural and technical evolution.

WSLUser commented 3 years ago

WT is not based on VTE at all, but does aim for Xterm compliance. And if you've been following the project, you could see there's alot of good stuff there to be learned from as much as there's plenty for them to learn from other terminals. When it comes to hashing, they've gotten a good story for it and recently optimized a bit for performance. But it's more hacky than they'd prefer and it's due to how Windows Terminal was built to start with. I'm not saying do something because a big company is doing it, I'm saying take advantage of lessons learned, especially if you've got a similar project, which Contour most certainly is. I would make comparisons to other terminals more except as I keep stating, WT is the most closely related terminal to Contour.

christianparpart commented 3 years ago

WT is not based on VTE at all, but does aim for Xterm compliance. And if you've been following the project, you could see there's alot of good stuff there to be learned from as much as there's plenty for them to learn from other terminals.

VTE := virtual terminal emulator

And accidentally also a library.

apart from that, i think all points have been made clear. There is nothing more to add to this ticket until an eventual implementation.

WSLUser commented 3 years ago

So I've just learned about https://github.com/martinus/robin-hood-hashing for boosting the performance of hashing and think it's better than the other 2 already listed, due to ensuring security is at it's optimal while also boosting performance. When this is implemented, I think this library should be used.

christianparpart commented 3 years ago

"Security"? ;-)

uspasojevic96 commented 3 years ago

So I've just learned about https://github.com/martinus/robin-hood-hashing for boosting the performance of hashing and think it's better than the other 2 already listed, due to ensuring security is at it's optimal while also boosting performance. When this is implemented, I think this library should be used.

i think you have some misconceptions about how maps work and hashing functions

jerch commented 3 years ago

I'd simply go for the fastest here. And since the possible search domain is quite small, I suggest to investigate, whether there exists a perfect hash function with very low calc needs. (@christianparpart Remember the aqit base63 decoder? Pretty fast with its perfect hash function).