On a host with ~1000 VMs (the support limit for XAPI) domain_getinfolist
took O(n^2) time (n=number of domains).
This couples with xenopsd making inefficient calls to
domain_getinfolist(1 call/VM) resulted in visibly bad performance of
XAPI.
It was calling the Xen domainfolist hypercall N/2 times.
Optimize this such that it is called at most 2 times during normal use.
Implement a tail recursive `rev_concat` equivalent to `concat |> rev`,
and use it instead of calling `@` multiple times.
The added benefit is that the list of domains should now actually be in
increasing order instead of having pairs of 2 changing direction every time.
Signed-off-by: Edwin Török <edvin.to...@citrix.com>
Tested-by: Pau Ruiz Safont <pau.saf...@citrix.com>
---
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 28ed642231..3ebedffdc7 100644
--- a/tools/ocaml/libs/xc/xenctrl.ml
+++ b/tools/ocaml/libs/xc/xenctrl.ml
@@ -226,14 +226,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"
--
2.34.1
