Improve performance when unmarshalling long vectors

pipcet commented 9 years ago

I noticed quite poor performance of xcb:keysyms:init (in excess of five seconds to run with the CPU at its slowest speed), and while I realize performance has not been a major concern so far, I believe this is worth fixing. It's due to this code in xcb-types.el:

        (dotimes (i list-size)
          (setq tmp (xcb:-unmarshal-field obj x data nil))
          (setq result (nconc result (list (car tmp))))
          (setq data (substring data (cadr tmp)))
          (setq count (+ count (cadr tmp))))

That's really inefficient if data is quite long, because substring doesn't appear to perform any optimizations in this case, so we perform O(n²) copying operations.

This patch avoids using substring and passes around the current offset into the data vector instead; that makes the code slightly more complicated, but I believe it is worth it as performance improves drastically. The critical code section turns into:

        (dotimes (i list-size)
          (setq tmp (xcb:-unmarshal-field obj x data (+ offset count) nil))
          (setq result (nconc result (list (car tmp))))
          (setq count (+ count (cadr tmp))))

with no modification of data.

Note that a corresponding change is needed in xelb-util: https://github.com/ch11ng/xelb-util/compare/master...pipcet:data-offset?expand=1

What do you think? I understand if you decide not to apply this patch because the complication isn't worth the performance gain, but I believe that it is.

ch11ng commented 9 years ago

I noticed the performance issue with xcb:keysyms:update-keyboard-mapping so I made ch11ng/exwm@24b964bb4af100b959a33215cc91b9c896c9359e, but I didn't find the reason. So if the performance issue is caused by substring, it's of course worth replacing it. Since this patch modifies the fundamental part of XELB, I need to carefully validate it.

pipcet commented 9 years ago

Thanks for responding!

Absolutely, take all the time you need, and please let me know if you find any problems so I can fix them and try again. There's also a minimal workaround that changes only the xcb:KEYSYM case at https://github.com/ch11ng/xelb/compare/master...pipcet:keysym-workaround?expand=1, but I must admit I really prefer the version that adds the offset argument everywhere.

(I haven't changed the xcb:unmarshal API, just xcb:-unmarshal-*; on the one hand, that means no public API change, but on the other hand, it means that extended types will always have a performance problem when used in long vectors. I still think it's early enough to change that, but it's obviously not a decision to be taken lightly. I think it might make most sense to add an xcb:unmarshal-at method and switch to that if it becomes necessary.)

ch11ng commented 9 years ago

Hi Pip,

I am sorry for having kept you waiting for so long. I think it's okay to merge this pull request. Before that, please make some minor fixes (all in xcb-types.el):

(substring data offset list-size) should be (substring data offset (+ list-size offset)) I think
That (list initform list-size) is dead code
Wrap long lines at 80 characters

And also, please open a pull request including those changes to xcb-icccm.el.

BTW, I want to merge xelb-util into xelb so that we can make a single package. What do you think?

Thank you!

pipcet commented 9 years ago

I am sorry for having kept you waiting for so long.

No problem at all.

I think it's okay to merge this pull request.

Excellent!

Before that, please make some minor fixes (all in xcb-types.el):

Done. Do let me know if you find anything else, please, I'm happy to do further cleanup.

And also, please open a pull request including those changes to xcb-icccm.el.

Done.

BTW, I want to merge xelb-util into xelb so that we can make a single package. What do you think?

I think that's an excellent idea, I'm wholly in favor of it.

ch11ng / xelb

Improve performance when unmarshalling long vectors #2