While using iproute2 in batch mode i notice that adding 11362 rules, on system 
with 500+ interfaces takes up to 1minute on Xeon 3.0 Ghz.
After "oprofiling" i got result:

CPU: P4 / Xeon with 2 hyper-threads, speed 2992.84 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events (time during which processor is not 
stopped) with a unit mask of 0x01 (mandatory) count 100000
samples  %        image name               symbol name
86166    57.3473  tc                       ll_remember_index
48103    32.0147  tc                       parse_rtattr
8497      5.6551  tc                       rtnl_dump_filter
1751      1.1654  [vdso] (tgid:22801 range:0xb7f66000-0xb7f67000) (no symbols)
1085      0.7221  tc                       tc_calc_xmittime
672       0.4472  tc                       .plt

I did small patch, and voila! batch finished in 2 seconds successfully!

Proof of concept patch is attached. Not sure if it is not breaking any other 
things. Waiting for any comments.