|
|
Chromium Code Reviews|
Created:
4 years ago by cavalcantii1 Modified:
3 years, 11 months ago Reviewers:
msarett, fmalita1, esprehn, Justin Novosad, Simon Hosie, schenney, msarett1, Nico, scroggo_chromium, xlai, xlai (Olivia) CC:
blink-reviews, chromium-reviews, reed1 Target Ref:
refs/pending/heads/master Project:
chromium Visibility:
Public. |
DescriptionNEON-ize RGBA to RGB code
The code path alone was made at least 4x faster than the original
(from 85us to 14us in a Nexus 6), lowering the runtime of pixel
conversion in 1/4 (e.g. from 330ms to 77ms in a 4K canvas).
This yields a global improvement of about 15% while calling
canvas.toBlob() and toDataURL() when the output format is JPEG and
canvas is hardware accelerated.
BUG=674264
Review-Url: https://codereview.chromium.org/2576223002
Cr-Commit-Position: refs/heads/master@{#442218}
Committed: https://chromium.googlesource.com/chromium/src/+/b630fb4deab73deea701d7122154a2835dbdf7fc
Patch Set 1 #
Total comments: 1
Patch Set 2 : Copyright, fix Windows build. #
Total comments: 6
Patch Set 3 : lambda and vraddhn #Patch Set 4 : Updating comments #
Total comments: 2
Patch Set 5 : Remove TODO, enable test, const-ify vars #Patch Set 6 : Windows Build++ #Patch Set 7 : Rebased (solved conflict in BUILD.GN) #
Total comments: 5
Patch Set 8 : Moved perf test to another issue #
Messages
Total messages: 84 (52 generated)
The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
cavalcantii@chromium.org changed reviewers: + esprehn@chromium.org, fmalita@gmail.com, schenney@google.com, simon.hosie@arm.com, thakis@chromium.org
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: win_chromium_compile_dbg_ng on master.tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_comp...)
Super cool! Can we get SSE3 optimizations like this for desktop too? Does this also make toDataURL() faster? https://codereview.chromium.org/2576223002/diff/1/third_party/WebKit/Source/p... File third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoderTest.cpp (right): https://codereview.chromium.org/2576223002/diff/1/third_party/WebKit/Source/p... third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoderTest.cpp:2: * Copyright 2016 The Chromium Authors. All rights reserved. Use the new short copyright on new files.
Description was changed from ========== NEON-ize RGBA to RGB code The code path alone was made at least 3x faster than the original (from 85us to 15us in a Nexus 6), lowering the runtime of pixel conversion in 1/3 (e.g. from 330ms to 90ms in a 4K canvas). This yields a global improvement of about 12% while calling canvas.toBlob() when the output format is JPEG and canvas is hardware accelerated. BUG=674264 ========== to ========== NEON-ize RGBA to RGB code The code path alone was made at least 3x faster than the original (from 85us to 15us in a Nexus 6), lowering the runtime of pixel conversion in 1/3 (e.g. from 330ms to 90ms in a 4K canvas). This yields a global improvement of about 12% while calling canvas.toBlob() when the output format is JPEG and canvas is hardware accelerated. BUG=674264 ==========
fmalita@chromium.org changed reviewers: + msarett@chromium.org, scroggo@chromium.org
Elliott Thanks for the comments, I will address the questions below: > Super cool! Can we get SSE3 optimizations like this for desktop too? I'm not an expert on SSE3, my guess is yes. On the bright side, the test suite should make really easy to validate other implementations. >Does this > also make toDataURL() faster? > I looked in the source code and it seems that the same code path is used for toDataURL() and a trace confirmed it. > https://codereview.chromium.org/2576223002/diff/1/third_party/WebKit/Source/p... > third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoderTest.cpp:2: * > Copyright 2016 The Chromium Authors. All rights reserved. > Use the new short copyright on new files. Coolio, will fix it. In a side note, I will next look into why the Windows bot is red.
Great! This patch looks good to me, but I'd like someone who works on the image decoders more closely to also look at it. btw how does going from 330ms -> 90ms only result in a 12% improvement? What are the total numbers in your benchmark?
Elliott In a Nexus 6 it takes around 2000ms to run the benchmark (http://codepen.io/Savago/pen/dOKPWM). Keep in mind that YMMV thanks to EAS and CPUFreq (expect a variation of 1600 to 2200ms). That being said, the improvements this patch brought were consistent and easily observed when adding tracing information at the beginning of RGBAtoRGB methods. Concerning the 12% improvement: I noticed that a considerable amount of time is being spent on GLES2::ReadPixels (see the trace screenshot in https://bugs.chromium.org/p/chromium/issues/detail?id=674264) which I'm planning to work next and see if we can make the code faster. It shouldn't take longer to just read the pixels than it takes to transform it and compress to JPEG. Finally, if I understood the code correctly, the image encoding process is scheduled to run as a task. In vanilla the cost of scheduling is really low compared to the time it takes to execute RGBAtoRGB (e.g. 0.005ms added to 0.090ms per function execution, so around 5%) but after the code was made vectorial it is significant (e.g. 0.005ms added to 0.0015ms, so around 25%). I'm planning in a follow up patch to group more calls per task execution (e.g. execute 5 lines instead of 1 line), because we would still be within the same time budget. The last but not the least, I noticed that the pixels seem to be stored in a contiguous array. That could be exploited to try to avoid paying the cost of many function calls (e.g. height of 4000 equals to 4000 function calls). The whole point is that there is a lot of margin to make this even faster. :-)
The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
cavalcantii@chromium.org changed reviewers: + junov@chromium.org
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
A higher level question (not necessarily relevant to this CL): Is there a way for us to know if the input is opaque? This is most likely the common case for someone who wants to encode to jpeg (jpegs are always opaque). This blending just simulates src-over onto a black background. But there might be the opportunity to (sometimes) skip this altogether. https://codereview.chromium.org/2576223002/diff/20001/third_party/WebKit/Sour... File third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoder.cpp (right): https://codereview.chromium.org/2576223002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoder.cpp:49: void RGBAtoRGBScalar(const unsigned char* pixels, libjpeg-turbo actually supports RGBA input (in addition to RGB). So RGBA to RGBA would actually be fine here. And would probably be faster (in the scalar code) in the case where we have opaque pixels. I don't think it would affect the NEON code much either way. Just a comment, no need to think about this in this change. https://codereview.chromium.org/2576223002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoder.cpp:97: low = vrsraq_n_u16(low, low, 8); Skia has a NEON implementation of "mul and rounded divide by 255". Probably worth taking a look, it takes advantage of vraddhn_u16(). https://cs.chromium.org/chromium/src/third_party/skia/src/opts/SkSwizzler_opt... https://codereview.chromium.org/2576223002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoder.cpp:106: // Now the Green channel (don't trust the compiler to unroll the loop). What about using an inline helper function? Ex: mul_div_255_round()
https://codereview.chromium.org/2576223002/diff/20001/third_party/WebKit/Sour... File third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoder.cpp (right): https://codereview.chromium.org/2576223002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoder.cpp:49: void RGBAtoRGBScalar(const unsigned char* pixels, On 2016/12/16 13:07:54, msarett1 wrote: > libjpeg-turbo actually supports RGBA input (in addition to RGB). So RGBA to > RGBA would actually be fine here. And would probably be faster (in the scalar > code) in the case where we have opaque pixels. > > I don't think it would affect the NEON code much either way. > > Just a comment, no need to think about this in this change. Acknowledged. https://codereview.chromium.org/2576223002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoder.cpp:97: low = vrsraq_n_u16(low, low, 8); On 2016/12/16 13:07:54, msarett1 wrote: > Skia has a NEON implementation of "mul and rounded divide by 255". Probably > worth taking a look, it takes advantage of vraddhn_u16(). > https://cs.chromium.org/chromium/src/third_party/skia/src/opts/SkSwizzler_opt... I searched for SkSwizzler_opts.h and it seems it is used only internally in Skia? I also noticed that scale() and div255_round() are both marked as 'static' but not inline. I wonder what happens at the call sites. Anyway, I got curious about the difference between using vrsra() X vraddhn(). Notice that in both cases you have to perform a shift, so the number of instructions is the same. What I think is troubling is that vraddhn requires a temporary register to keep the result of shifting x (while vrsra doesn't need that). That being said, ARM has quite a few registers. :-) I decided to have a look on how the assembly would look like for each version. a) Using vraddhn: https://godbolt.org/g/Ji8cmW b) Using vrsra: https://godbolt.org/g/XHe9ky And after next I executed the test4KPerf 20x times (Nexus 6) for each version and collected this data: https://gist.github.com/Adenilson/ff2d677ce4cb16662e406fbe497053c9 It seems that using vraddhn is about 6% faster (mraddh/mrsra = 0.9483218), but not in a conclusive way (reported F was 0.47). Since both implementations pass the test suite, I'm ok with going with vraddhn. A question: what would be the right way of adding the Skia header in JPEGImageEncoder? https://codereview.chromium.org/2576223002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoder.cpp:106: // Now the Green channel (don't trust the compiler to unroll the loop). On 2016/12/16 13:07:54, msarett1 wrote: > What about using an inline helper function? Ex: mul_div_255_round() I tested moving the pixel manipulation code to a lambda and the compiler was able to inline it just fine (as long using at least -O1).
The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Just added in the issue a screenshot of a trace using vradd: https://bugs.chromium.org/p/chromium/issues/detail?id=674264#c8 It dropped the walltime from 90ms to 77ms.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
@msarret1 In a second thought, it seems a bit overkill to import a whole header file for just 2 lines of code. If it is ok, I will upload a patch using vmull/vraddhn integrated in transformColor().
msarett@google.com changed reviewers: + msarett@google.com
lgtm, though you'll still need an OWNER review https://codereview.chromium.org/2576223002/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoder.cpp (right): https://codereview.chromium.org/2576223002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoder.cpp:71: // how to include it? Sorry for being unclear, there's no plan to make the Skia code public. I was suggesting looking at it just to try out the implementation, not to make you worry about code sharing. You can remove this TODO :). https://codereview.chromium.org/2576223002/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoderTest.cpp (right): https://codereview.chromium.org/2576223002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/platform/image-encoders/JPEGImageEncoderTest.cpp:38: #ifdef __ARM_NEON__ Is there a reason to only test on Arm NEON? This seems like a good test to run on all platforms.
The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Description was changed from ========== NEON-ize RGBA to RGB code The code path alone was made at least 3x faster than the original (from 85us to 15us in a Nexus 6), lowering the runtime of pixel conversion in 1/3 (e.g. from 330ms to 90ms in a 4K canvas). This yields a global improvement of about 12% while calling canvas.toBlob() when the output format is JPEG and canvas is hardware accelerated. BUG=674264 ========== to ========== NEON-ize RGBA to RGB code The code path alone was made at least 4x faster than the original (from 85us to 14us in a Nexus 6), lowering the runtime of pixel conversion in 1/4 (e.g. from 330ms to 77ms in a 4K canvas). This yields a global improvement of about 15% while calling canvas.toBlob() and toDataURL() when the output format is JPEG and canvas is hardware accelerated. BUG=674264 ==========
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: linux_chromium_chromeos_rel_ng on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...) mac_chromium_rel_ng on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)
Patchset #5 (id:80001) has been deleted
The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: cast_shell_android on master.tryserver.chromium.android (JOB_FAILED, https://build.chromium.org/p/tryserver.chromium.android/builders/cast_shell_a...)
Patchset #5 (id:100001) has been deleted
The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
@Matt Thanks for the review (and specially for the suggestion concerning vraddhn). I will comment inline. > > You can remove this TODO :). Done. > #ifdef __ARM_NEON__ > Is there a reason to only test on Arm NEON? This seems like a good test to run > on all platforms. It is enabled now.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: win_chromium_rel_ng on master.tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_rel_...)
The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
Rebased with master.
lgtm
FYI: I'd really prefer someone like fmalita@ or schenny@ look at this. You should email them too.
Elliott Thanks for the review. IIRC, I've added them in the issue since the beginning.
On 2017/01/05 at 00:15:52, cavalcantii wrote: > Elliott > > Thanks for the review. > > IIRC, I've added them in the issue since the beginning. I know, but they haven't been replying. I'd send them some direct emails instead.
> I know, but they haven't been replying. I'd send them some direct emails > instead. Coolio, just emailed them.
https://codereview.chromium.org/2576223002/diff/160001/third_party/WebKit/Per... File third_party/WebKit/PerformanceTests/Canvas/toBlob_duration_jpeg.html (right): https://codereview.chromium.org/2576223002/diff/160001/third_party/WebKit/Per... third_party/WebKit/PerformanceTests/Canvas/toBlob_duration_jpeg.html:1: <!DOCTYPE html> Would be better to land the performance test first, in a separate CL and let it run for a few cycles. Then land the fix. That way we will be able to observe the improvement on the bots. https://codereview.chromium.org/2576223002/diff/160001/third_party/WebKit/Per... third_party/WebKit/PerformanceTests/Canvas/toBlob_duration_jpeg.html:36: draw(); //repeatedly draw the frame to keep main thread busy It is not clear why this is necessary. Won't this just make the test results a bit noisier? Also, draw() does nothing except schedule the next draw, so how is this keeping the thread busy?
https://codereview.chromium.org/2576223002/diff/160001/third_party/WebKit/Per... File third_party/WebKit/PerformanceTests/Canvas/toBlob_duration_jpeg.html (right): https://codereview.chromium.org/2576223002/diff/160001/third_party/WebKit/Per... third_party/WebKit/PerformanceTests/Canvas/toBlob_duration_jpeg.html:1: <!DOCTYPE html> I did thought about that, but do we have an android perf bot? And does it run this tests? https://codereview.chromium.org/2576223002/diff/160001/third_party/WebKit/Per... third_party/WebKit/PerformanceTests/Canvas/toBlob_duration_jpeg.html:36: draw(); //repeatedly draw the frame to keep main thread busy I just based this test on: https://cs.chromium.org/chromium/src/third_party/WebKit/PerformanceTests/Canv... If it is an issue, should it be fixed too?
junov@chromium.org changed reviewers: + xlai@google.com
+xlai To comment on the busy loop in the toBlob test
On 2017/01/05 16:16:15, cavalcantii1 wrote: > https://codereview.chromium.org/2576223002/diff/160001/third_party/WebKit/Per... > File third_party/WebKit/PerformanceTests/Canvas/toBlob_duration_jpeg.html > (right): > > https://codereview.chromium.org/2576223002/diff/160001/third_party/WebKit/Per... > third_party/WebKit/PerformanceTests/Canvas/toBlob_duration_jpeg.html:1: > <!DOCTYPE html> > I did thought about that, but do we have an android perf bot? And does it run > this tests? > Yes, ther are plenty of Android bots running these tests. For example: https://chromeperf.appspot.com/report?sid=eb0b0f6fe2d23a9bfd13b936d1109421779... There had better be, otherwise the test would have been irrelevent to this CL.
xlai@chromium.org changed reviewers: + xlai@chromium.org
https://codereview.chromium.org/2576223002/diff/160001/third_party/WebKit/Per... File third_party/WebKit/PerformanceTests/Canvas/toBlob_duration_jpeg.html (right): https://codereview.chromium.org/2576223002/diff/160001/third_party/WebKit/Per... third_party/WebKit/PerformanceTests/Canvas/toBlob_duration_jpeg.html:36: draw(); //repeatedly draw the frame to keep main thread busy On 2017/01/05 16:16:15, cavalcantii1 wrote: > I just based this test on: > https://cs.chromium.org/chromium/src/third_party/WebKit/PerformanceTests/Canv... > > If it is an issue, should it be fixed too? Actually, this test was initially created to compare the idle v.s. threaded versions of toBlob implementation; but later, a more useful performance test (https://cs.chromium.org/chromium/src/tools/perf/page_sets/tough_canvas_cases/...) was added to measure the jankiness of toBlob on main thread, which is a more relevant benchmark for our previous task of comparing idle v.s. threaded. As a result, this toBlob_duration.html becomes simply a safeguard test to prevent someone else committing code that makes the png encoding process longer (I think some time ago there was a patch that touched the png encoder get reverted because of this). IMHO, when the test is serving this purpose, deliberately making the main thread busy on drawing is no longer very important. In this regard, probably we can just remove this busy draw loop here.
On 2017/01/05 20:13:57, xlai (Olivia) wrote: > > Actually, this test was initially created to compare the idle v.s. > threaded versions of toBlob implementation; but later, a more useful > performance test > (https://cs.chromium.org/chromium/src/tools/perf/page_sets/tough_canvas_cases/...) > was added to measure the jankiness of toBlob on main thread, > which is a more relevant benchmark for our previous task of comparing > idle v.s. threaded. > > As a result, this toBlob_duration.html becomes simply a safeguard test to > prevent someone else committing code that makes the png encoding process > longer (I think some time ago there was a patch that touched the png > encoder get reverted because of this). IMHO, when the test is serving > this purpose, deliberately making the main thread busy on drawing > is no longer very important. In this regard, probably we can just remove > this busy draw loop here. So if I understand correctly, the original idea was to make the scheduler generate a succession of idle periods in between rAF callbacks. Since scheduling jank is covered elsewhere now, I agree that we should remove this rAF loop.
The CQ bit was checked by cavalcantii@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
@xlai Thanks for the input, it was quite enlightening. @junov I created an issue for the HTML perf test. The idea would be to first upload it followed next by the NEON optimizations. How many days you feel it would be enough for the bot to create a 'baseline' so we can upload the second patch?
For reference, the test is now in: https://codereview.chromium.org/2617843002/
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
> @junov > I created an issue for the HTML perf test. > > The idea would be to first upload it followed next by the NEON optimizations. > > How many days you feel it would be enough for the bot to create a 'baseline' so > we can upload the second patch? The similar test that already existed was not very noisy on Android so Ì don't think we need a lot of data points. One day should be plenty.
This patch lgtm
The test landed 2 days ago, I'm adding the patch to the CQ.
The CQ bit was checked by cavalcantii@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from msarett@google.com, esprehn@chromium.org Link to the patchset: https://codereview.chromium.org/2576223002/#ps180001 (title: "Moved perf test to another issue")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
CQ is committing da patch.
Bot data: {"patchset_id": 180001, "attempt_start_ts": 1483949227748550,
"parent_rev": "b4650e3759f9d61f76ea15e6f022464fbb3d1de8", "commit_rev":
"b630fb4deab73deea701d7122154a2835dbdf7fc"}
Message was sent while issue was closed.
Description was changed from ========== NEON-ize RGBA to RGB code The code path alone was made at least 4x faster than the original (from 85us to 14us in a Nexus 6), lowering the runtime of pixel conversion in 1/4 (e.g. from 330ms to 77ms in a 4K canvas). This yields a global improvement of about 15% while calling canvas.toBlob() and toDataURL() when the output format is JPEG and canvas is hardware accelerated. BUG=674264 ========== to ========== NEON-ize RGBA to RGB code The code path alone was made at least 4x faster than the original (from 85us to 14us in a Nexus 6), lowering the runtime of pixel conversion in 1/4 (e.g. from 330ms to 77ms in a 4K canvas). This yields a global improvement of about 15% while calling canvas.toBlob() and toDataURL() when the output format is JPEG and canvas is hardware accelerated. BUG=674264 Review-Url: https://codereview.chromium.org/2576223002 Cr-Commit-Position: refs/heads/master@{#442218} Committed: https://chromium.googlesource.com/chromium/src/+/b630fb4deab73deea701d7122154... ==========
Message was sent while issue was closed.
Committed patchset #8 (id:180001) as https://chromium.googlesource.com/chromium/src/+/b630fb4deab73deea701d7122154... |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
