use gnuhash to speed up device/driver match
cover use gnuhash to speed up device/driver match
Hi,
The following patch series use the gnu hash to speedup device/driver matching.
String compare is slow so we will calculate at runtime a hash that we can compare quickly to speed up the match
in a second step we could speed up this more by calculating the hash at compile time
The following changes since commit d92ed454107b4d6f0d30fa0271da191ae5911d18:
Merge branch 'for-next/video' into next (2017-02-27 08:51:08 +0100)
are available in the git repository at:
git://git.jcrosoft.org/barebox.git delivery/gnuhash
for you to fetch changes up to 5ede85afc958bdf488a3c5e56061e7f27c26cbc6:
driver: generate hash at runtime to speed up device/driver matching (2017-03-01 03:49:34 +0800)
----------------------------------------------------------------
Jean-Christophe PLAGNIOL-VILLARD (2):
driver: remove the const of struct platform_device_id *id_table
driver: generate hash at runtime to speed up device/driver matching
drivers/base/bus.c | 16 ++++++++++------ drivers/base/driver.c | 27 ++++++++++++++++++++++++++- include/driver.h | 7 ++++++- 3 files changed, 42 insertions(+), 8 deletions(-)
Best Regards,
J.
_______________________________________________
barebox mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/barebox
PATCH 1/2 driver: remove the const of struct platform_device_id *id_table
so we can generate the hash at register time
This will allow speed up the device/driver matching as strcmp is slow.
--- drivers/base/bus.c | 4 ++-- include/driver.h | 2 +- 2 files changed, 3 insertions(+), 3 deletions(-)
drivers/base/bus.c +2 -2
@@ -55,7 +55,7 @@ int device_match(struct device_d *dev, struct driver_d *drv)return of_match (dev, drv);if (drv->id_table) { -const struct platform_device_id *id = drv->id_table; +struct platform_device_id *id = drv->id_table;while (id->name) {if (!strcmp (id->name, dev->name)) {
@@ -73,7 +73,7 @@ int device_match(struct device_d *dev, struct driver_d *drv)int device_match_of_modalias (struct device_d *dev,struct driver_d *drv) { -const struct platform_device_id *id = drv->id_table; +struct platform_device_id *id = drv->id_table;const char *of_modalias =NULL , *p;int cplen;const char *compat;
include/driver.h +1 -1
@@ -107,7 +107,7 @@ struct driver_d {struct bus_type *bus; -const struct platform_device_id *id_table; +struct platform_device_id *id_table;const struct of_device_id *of_compatible; };
Signature · 7 lines
2.11.0 _______________________________________________ barebox mailing list [email protected] http://lists.infradead.org/mailman/listinfo/barebox
PATCH 2/2 driver: generate hash at runtime to speed up device/driver matching
use GNU Hash
--- drivers/base/bus.c | 12 ++++++++---- drivers/base/driver.c | 27 ++++++++++++++++++++++++++- include/driver.h | 5 +++++ 3 files changed, 39 insertions(+), 5 deletions(-)
drivers/base/bus.c +8 -4
@@ -58,13 +58,13 @@ int device_match(struct device_d *dev, struct driver_d *drv)struct platform_device_id *id = drv->id_table;while (id->name) { -if (!strcmp (id->name, dev->name)) { +if (dev->hash == id->hash && !strcmp (id->name, dev->name)) { dev->id_entry = id;return 0 ; } id++; } - }else if (!strcmp (dev->name, drv->name)) { + }else if (dev->hash == drv->hash && !strcmp (dev->name, drv->name)) {return 0 ; }
@@ -77,6 +77,7 @@ int device_match_of_modalias(struct device_d *dev, struct driver_d *drv)const char *of_modalias =NULL , *p;int cplen;const char *compat; +unsigned long hash;if (!device_match (dev, drv))return 0 ;
@@ -90,14 +91,17 @@ int device_match_of_modalias(struct device_d *dev, struct driver_d *drv) p =strchr (compat,',' ); of_modalias = p ? p +1 : compat; +if (of_modalias) + hash =gnu_hash (of_modalias);while (id->name) { -if (!strcmp (id->name, dev->name)) { +if (id->hash == dev->hash && !strcmp (id->name, dev->name)) { dev->id_entry = id;return 0 ; } -if (of_modalias && !strcmp (id->name, of_modalias)) { +if (of_modalias && id->hash == hash && + !strcmp (id->name, of_modalias)) { dev->id_entry = id;return 0 ; }
drivers/base/driver.c +26 -1
@@ -46,6 +46,17 @@ EXPORT_SYMBOL(driver_list);static LIST_HEAD (active);static LIST_HEAD (deferred); +unsigned long gnu_hash (const unsigned char *name) +{ +unsigned long h =5381 ; +unsigned char c; + +for (c = *name; c !='\0' ; c = *++name) + h = h *33 + c; + +return h &0xffffffff ; +} +struct device_d *get_device_by_name (const char *name) {struct device_d *dev;
@@ -61,9 +72,10 @@ struct device_d *get_device_by_name(const char *name)static struct device_d *get_device_by_name_id (const char *name,int id) {struct device_d *dev; +unsigned long hash =gnu_hash (name);for_each_device (dev) { -if (!strcmp (dev->name, name) && id == dev->id) +if (hash == dev->hash && !strcmp (dev->name, name) && id == dev->id)return dev; }
@@ -165,6 +177,8 @@ int register_device(struct device_d *new_device) {struct driver_d *drv; + new_device->hash =gnu_hash (new_device->name); +if (new_device->id ==DEVICE_ID_DYNAMIC ) { new_device->id =get_free_deviceid (new_device->name); }else {
@@ -302,6 +316,17 @@ int register_driver(struct driver_d *drv)BUG_ON (!drv->bus); + drv->hash =gnu_hash (drv->name); + +if (drv->id_table) { +struct platform_device_id *id = drv->id_table; + +while (id->name) { + id->hash =gnu_hash (id->name); + id++; + } + } +list_add_tail (&drv->list, &driver_list);list_add_tail (&drv->bus_list, &drv->bus->driver_list);
include/driver.h +5 -0
@@ -31,8 +31,11 @@struct filep ;struct bus_type ; +unsigned long gnu_hash (const unsigned char *name); +struct platform_device_id {const char *name; +unsigned long hash;unsigned long driver_data; };
@@ -42,6 +45,7 @@ struct device_d {* driver. This is a descriptive name and could be MPC5XXX_ether or * imx_serial. */ char name[MAX_DRIVER_NAME ]; +unsigned long hash;/*! The id is used to uniquely identify a device in the system. The id * will show up under /dev/ as the device's name. Usually this is * something like eth0 or nor0. */
@@ -95,6 +99,7 @@ struct driver_d {/*! The name of this driver. Used to match to * the corresponding device. */ const char *name; +unsigned long hash;struct list_head list;struct list_head bus_list;/* our bus */
Signature · 7 lines
2.11.0 _______________________________________________ barebox mailing list [email protected] http://lists.infradead.org/mailman/listinfo/barebox
Quoted 10 lines · Jean-Christophe PLAGNIOL-VILLARD
Hi,
The following patch series use the gnu hash to speedup device/driver matching.
String compare is slow so we will calculate at runtime a hash that we can compare quickly to speed up the match
in a second step we could speed up this more by calculating the hash at compile time
On a i.MX53 quickstart board this patch reduces startup time from 115.9ms to 115.4ms. On a i.MX35 board the startup time is reduced by 72us. I don't think this is a valuable gain. Do you have any situation where you really spend significant time in strcmp?
Sascha
Signature · 9 lines
Pengutronix e.K. | | Industrial Linux Solutions | http://www.pengutronix.de/ | Peiner Str. 6-8, 31137 Hildesheim, Germany | Phone: +49-5121-206917-0 | Amtsgericht Hildesheim, HRA 2686 | Fax: +49-5121-206917-5555 | _______________________________________________ barebox mailing list [email protected] http://lists.infradead.org/mailman/listinfo/barebox