commit 03f545b6cf3220b4647677b588e5525a781a4813
Author: Edwin Török <edvin.torok@citrix.com>
AuthorDate: Tue Nov 1 17:59:16 2022 +0000
Commit: Andrew Cooper <andrew.cooper3@citrix.com>
CommitDate: Thu Feb 9 15:55:25 2023 +0000
tools/ocaml/xenctrl: Make domain_getinfolist tail recursive
domain_getinfolist() is quadratic with the number of domains, because of the
behaviour of the underlying hypercall. xenopsd was further observed to be
wasting excessive quantites of time manipulating the list of already-obtained
domains.
Implement a tail recursive `rev_concat` equivalent to `concat |> rev`, and use
it instead of calling `@` multiple times.
An incidental benefit is that the list of domains will now be in domid order,
instead of having pairs of 2 domains changing direction every time.
In a scalability testing scenario with ~1000 VMs, a combination of this and
the subsequent change takes xenopsd's wallclock time in domain_getinfolist()
down from 88% to 0.02%
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Tested-by: Pau Ruiz Safont <pau.safont@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
(cherry picked from commit c3b6be714c64aa62b56d0bce96f4b6a10b5c2078)
---
tools/ocaml/libs/xc/xenctrl.ml | 23 +++++++++++++++++------
1 file changed, 17 insertions(+), 6 deletions(-)
diff --git a/tools/ocaml/libs/xc/xenctrl.ml b/tools/ocaml/libs/xc/xenctrl.ml
index 83e39a8616..85b73a7f6f 100644
--- a/tools/ocaml/libs/xc/xenctrl.ml
+++ b/tools/ocaml/libs/xc/xenctrl.ml
@@ -222,14 +222,25 @@ external domain_shutdown: handle -> domid -> shutdown_reason -> unit
external _domain_getinfolist: handle -> domid -> int -> domaininfo list
= "stub_xc_domain_getinfolist"
+let rev_append_fold acc e = List.rev_append e acc
+
+(**
+ * [rev_concat lst] is equivalent to [lst |> List.concat |> List.rev]
+ * except it is tail recursive, whereas [List.concat] isn't.
+ * Example:
+ * rev_concat [[10;9;8];[7;6];[5]]] = [5; 6; 7; 8; 9; 10]
+ *)
+let rev_concat lst = List.fold_left rev_append_fold [] lst
+
let domain_getinfolist handle first_domain =
let nb = 2 in
- let last_domid l = (List.hd l).domid + 1 in
- let rec __getlist from =
- let l = _domain_getinfolist handle from nb in
- (if List.length l = nb then __getlist (last_domid l) else []) @ l
- in
- List.rev (__getlist first_domain)
+ let rec __getlist lst from =
+ (* _domain_getinfolist returns domains in reverse order, largest first *)
+ match _domain_getinfolist handle from nb with
+ | [] -> rev_concat lst
+ | (hd :: _) as l -> __getlist (l :: lst) (hd.domid + 1)
+ in
+ __getlist [] first_domain
external domain_getinfo: handle -> domid -> domaininfo= "stub_xc_domain_getinfo"
--
generated by git-patchbot for /home/xen/git/xen.git#stable-4.17
Author: Edwin Török <edvin.torok@citrix.com>
AuthorDate: Tue Nov 1 17:59:16 2022 +0000
Commit: Andrew Cooper <andrew.cooper3@citrix.com>
CommitDate: Thu Feb 9 15:55:25 2023 +0000
tools/ocaml/xenctrl: Make domain_getinfolist tail recursive
domain_getinfolist() is quadratic with the number of domains, because of the
behaviour of the underlying hypercall. xenopsd was further observed to be
wasting excessive quantites of time manipulating the list of already-obtained
domains.
Implement a tail recursive `rev_concat` equivalent to `concat |> rev`, and use
it instead of calling `@` multiple times.
An incidental benefit is that the list of domains will now be in domid order,
instead of having pairs of 2 domains changing direction every time.
In a scalability testing scenario with ~1000 VMs, a combination of this and
the subsequent change takes xenopsd's wallclock time in domain_getinfolist()
down from 88% to 0.02%
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Tested-by: Pau Ruiz Safont <pau.safont@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
(cherry picked from commit c3b6be714c64aa62b56d0bce96f4b6a10b5c2078)
---
tools/ocaml/libs/xc/xenctrl.ml | 23 +++++++++++++++++------
1 file changed, 17 insertions(+), 6 deletions(-)
diff --git a/tools/ocaml/libs/xc/xenctrl.ml b/tools/ocaml/libs/xc/xenctrl.ml
index 83e39a8616..85b73a7f6f 100644
--- a/tools/ocaml/libs/xc/xenctrl.ml
+++ b/tools/ocaml/libs/xc/xenctrl.ml
@@ -222,14 +222,25 @@ external domain_shutdown: handle -> domid -> shutdown_reason -> unit
external _domain_getinfolist: handle -> domid -> int -> domaininfo list
= "stub_xc_domain_getinfolist"
+let rev_append_fold acc e = List.rev_append e acc
+
+(**
+ * [rev_concat lst] is equivalent to [lst |> List.concat |> List.rev]
+ * except it is tail recursive, whereas [List.concat] isn't.
+ * Example:
+ * rev_concat [[10;9;8];[7;6];[5]]] = [5; 6; 7; 8; 9; 10]
+ *)
+let rev_concat lst = List.fold_left rev_append_fold [] lst
+
let domain_getinfolist handle first_domain =
let nb = 2 in
- let last_domid l = (List.hd l).domid + 1 in
- let rec __getlist from =
- let l = _domain_getinfolist handle from nb in
- (if List.length l = nb then __getlist (last_domid l) else []) @ l
- in
- List.rev (__getlist first_domain)
+ let rec __getlist lst from =
+ (* _domain_getinfolist returns domains in reverse order, largest first *)
+ match _domain_getinfolist handle from nb with
+ | [] -> rev_concat lst
+ | (hd :: _) as l -> __getlist (l :: lst) (hd.domid + 1)
+ in
+ __getlist [] first_domain
external domain_getinfo: handle -> domid -> domaininfo= "stub_xc_domain_getinfo"
--
generated by git-patchbot for /home/xen/git/xen.git#stable-4.17