for the record - I am testing on openwrt: mips (wndr3800), mipsel (edgerouterx), arm (dual core A15), APU2 (low end amd x86), , and periodically a couple nanostation or picostations that are lying around. Got cross compilation for any given version kind of automated now. It's all openwrt 18.6 + builds of babel
on ubuntu 16, is a intel quad core atom, core i3, 1 12 core olde xeons on ubuntu 18 1 12 core xeon, 1 apu2 Anyway... The last major place where babeld goes asymptotic is when you have a lot of announcements, retractions and other shifts of metrics going on. There's a linked list over in resend.c that gets scanned, and rescanned, a lot, and that shows up in a gprof when you have that level of churn going on and having that cpu get bloated causes carnage elsewhere. It didn't seem like the route_stream idea or periodic sorting would help here, but a semi-permanent structure. I first tried rbtrees (which worked well, but deletion was a PITA, I can put that version up if someone wants it), then I reached for an old standby, the uthash file which supports O(1) hash lookups, O(1) deletion (from a doubly linked list), and other stuff (aside from the hash cost) that makes it really fast.... The result in resend.c looks kind of pretty, IMHO https://github.com/dtaht/babeld-hacking/blob/5856c729e3f883e043889a1b8a3caa407de54674/resend.c And even the uthash.h is not too hard on the eyes. (bird has a *nice* hash lib, too) The nlogn performance improvement for xroute imports was really helpful (aside from the redistribute bug), but when you're churning, the uthashed resend.c kept things much more sane on top of that. with the nlogn + uthash, well, I got to ~64k routes... or 16k with lots of intentional churn. So: If anyone wants to try it: This is a merge of what I just tested over the past week on top of the nlogn branch: https://github.com/dtaht/babeld-hacking/commits/nlogn-uthash-merge which just has the uthash of resend.c in it. this is my ongoing branch effort (on top of rfc6126bis) to make all of the babel structures hashable. https://github.com/dtaht/babeld-hacking/commits/uthash which I think might have potential in a post "dev" "datum" structure world in particular. I started on it with the idea that if everything ended up hashed, and quickly sortable, and immediately deletable... life might be better. I have to admire the route_stream idea and how parsimonious babel currently is with memory, but with each malloc pointer eating? 24 bytes on 64 bit arches? (I don't remember) + the typical size of a babel structure + uthash (54 bytes), it didn't seem like it would hurt all that much... and if you only hash once (post-datum branch)... and join on that hash value.... oooooh..... :) Still... A) I don't like scanning for garbage whilst otherwise really busy (me and GC have a lot of frustrated history together in the realtime world). timerwheels... B) still want to get the hellos in and out no matter what else is going on... I have had the most time to fiddle with babeld the past month in years, and I have to say, I really admire it. So much functionality in so little code. _______________________________________________ Babel-users mailing list [email protected] https://alioth-lists.debian.net/cgi-bin/mailman/listinfo/babel-users
