GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing github.com — Reduce allocations in Get-Content cmdlet by iSazonov · Pull Request #8103 · PowerShell/PowerShell

Conversation

Ilya (iSazonov) commented Oct 22, 2018 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Collaborator

PR Summary

Current implementation do huge extra allocations for every line of a file and at worst for every char (!). The fix exclude the extra allocations by moving initializations in a constructor and using Span for temporary buffer.

The Boyer-Moore string search algorithm was optimized. Use simple mapping Unicode chars to byte. It works well for common text files with chars from one-two languages.

You could review commit by commit.

PR Checklist

PR has a meaningful title
- Use the present tense and imperative mood when describing your changes
Summarized changes
Change is not breaking
Make sure all .h, .cpp, .cs, .ps1 and .psm1 files have the correct copyright header
This PR is ready to merge and is not Work in Progress.
- If the PR is work in progress, please add the prefix WIP: to the beginning of the title and remove the prefix when the PR is ready.
User-facing changes
- Not Applicable
- OR
- User-facing Documentation needed
  - Issue filed - Issue link:
Testing - New and feature
- Not Applicable or can only be tested interactively
- OR
- Make sure you've added a new test if existing tests do not effectively test the code changed
  - Add [feature] if the change is significant or affects feature tests

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Ilya (iSazonov) added 6 commits

October 22, 2018 16:17


          Simplify main loop in ReadDelimited() by bringing out raw stream code

29705ce


          Remove unused constructor

d0528f3


          Allocate offset lookups dictionary only for non-default delimiter

afef290


          Allocate buffer for current line once in constructor

004cce2


          Use Span buffer to significantly reduce allocations

8a2dc06


          Fix comment

d6f6c11

Ilya (iSazonov) requested review from Bruce Payette (BrucePay) and Andrew (anmenaga) as code owners

October 22, 2018 14:14

Ilya (iSazonov) requested review from Steve Lee (SteveL-MSFT) and Aditya Patwardhan (adityapatwardhan)

October 22, 2018 14:15

Ilya (iSazonov) self-assigned this

Oct 22, 2018

Andrew (anmenaga) reviewed

Oct 22, 2018

View reviewed changes

Comment thread

src/System.Management.Automation/namespaces/FileSystemContentStream.cs

		/// <param name="isRawStream">
		/// Indicates raw stream.
		/// </param>
		public FileSystemContentReaderWriter(

Andrew (anmenaga) Oct 22, 2018

Copy link

Copy Markdown

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why was this removed?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Ilya (iSazonov) Oct 24, 2018

Copy link

Copy Markdown

Collaborator Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It is unneeded and used internal constructor and we can safely remove it. (Otherwise we have to fix it to follow our changes in another constructor with delimiter parameter.)

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions


          Fix Style issues

7c2dc6f

Paul Higinbotham (PaulHigin) suggested changes

Oct 23, 2018

View reviewed changes

Paul Higinbotham (PaulHigin) left a comment

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Overall this looks good to me. I agree that the offset Dictionary could be a perf issue for simple delimiter characters. Have you performed any tests to verify perf gains? I imagine they would be significant, in some case, by switching to use Span.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

src/System.Management.Automation/namespaces/FileSystemContentStream.cs Outdated

		blocks.Add(contentRead);
		}

		return _reader.Peek() != -1;

Paul Higinbotham (PaulHigin) Oct 23, 2018

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Doesn't this always have to be -1, when reading a raw stream to the end?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

iSazonov reacted with thumbs up emoji

All reactions

👍 1 reaction

Ilya (iSazonov) Oct 24, 2018

Copy link

Copy Markdown

Collaborator Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

src/System.Management.Automation/namespaces/FileSystemContentStream.cs Outdated

		// we can read to generate another possible match.
		// If we read more characters than this, we risk consuming
		// more of the stream than we need.
		_offsetDictionary = new Dictionary<char, int>(_delimiter.Length);

Paul Higinbotham (PaulHigin) Oct 23, 2018

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks a little bit dangerous. If _usingDelimiter is set to true anywhere else, _currentLineContent, _offsetDictionary will be null during later reads. I feel we should at least have an assert where these are used to ensure they are not null and as a warning if the code somehow gets changed.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Ilya (iSazonov) Oct 24, 2018

Copy link

Copy Markdown

Collaborator Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If somebody make the wrong change our tests will be crashed with null reference exception and we'll never merge the code. I don't know where we could set the assert and how it can help more then the null reference exception.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions


          Address feedback

20274dc

Ilya (iSazonov) commented Oct 24, 2018 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Collaborator Author

I agree that the offset Dictionary could be a perf issue for simple delimiter characters.

I don't found how quickly fix this. Will investigate.

Have you performed any tests to verify perf gains?

No. I accidentally discovered this by reading code. Once I realized that we allocate in heap for every char in a worst case and for every line I did not see the point to run PerfView.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

Ilya (iSazonov) requested review from Travis Plunk (TravisEz13) and Dongbo Wang (daxian-dbw) as code owners

October 24, 2018 11:18


          Optimize Boyer-Moore

Paul Higinbotham (PaulHigin) reviewed

Oct 24, 2018

View reviewed changes

Comment thread

src/System.Management.Automation/namespaces/FileSystemContentStream.cs Outdated

Paul Higinbotham (PaulHigin) Oct 24, 2018

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think this can be

_offsetDictionary[lowByte] = _delimiter.Length - i - 1;

For duplicate chars the last index will end up in _offsetDictionary[lowByte]

Also, do we need to be worried about char collisions using the low byte?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Ilya (iSazonov) Oct 25, 2018

Copy link

Copy Markdown

Collaborator Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Also, do we need to be worried about char collisions using the low byte?

There is a comment in the code. If we have a file with chars from many languages we'll have many collisions and lost performance. In practice, we can expect that files contains chars from one-two languages. In the common case we'll have no collisions and best performance.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Ilya (iSazonov) Oct 25, 2018 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Collaborator Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think this can be

Thanks! Good catch!

Fixed.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Paul Higinbotham (PaulHigin) reviewed

Oct 24, 2018

View reviewed changes

Comment thread

src/System.Management.Automation/namespaces/FileSystemContentStream.cs Outdated

Paul Higinbotham (PaulHigin) Oct 24, 2018

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

currentChar can be defined below where it is used.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Ilya (iSazonov) Oct 25, 2018

Copy link

Copy Markdown

Collaborator Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions


          Fix _offsetDictionary init

07af4ca

Ilya (iSazonov) force-pushed the optimizations-in-getcontent2 branch from 4a7488a to 07af4ca Compare

October 25, 2018 04:52

Ilya (iSazonov) added 2 commits

October 25, 2018 09:55


          Fix var init

244890f


          Fix style issue

f0c0898

Paul Higinbotham (PaulHigin) approved these changes

Oct 25, 2018

View reviewed changes

Paul Higinbotham (PaulHigin) left a comment

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Ilya (iSazonov) commented Oct 25, 2018

Copy link

Copy Markdown

Collaborator Author

Andrew (@anmenaga) Steve Lee (@SteveL-MSFT) Have you any comments?

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

Andrew (anmenaga) commented Oct 25, 2018

Copy link

Copy Markdown

Get-Content is a frequently used cmdlet. I would like to see a green [feature] test run for this. Thanks.

iSazonov reacted with thumbs up emoji

All reactions

👍 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.


          [Feature]

09db90e

Ilya (iSazonov) merged commit 0e19042 into PowerShell:master

Oct 26, 2018

Ilya (iSazonov) deleted the optimizations-in-getcontent2 branch

October 26, 2018 03:56

Thatgfsj (Thatgfsj) pushed a commit to Thatgfsj-contribs/PowerShell that referenced this pull request

Aug 6, 2026


          Reduce allocations in Get-Content cmdlet (PowerShell#8103)

270d7a2

* Simplify main loop in ReadDelimited() by bringing out raw stream code
* Remove unused constructor
* Allocate buffer for current line once in constructor
* Use Span buffer to significantly reduce allocations
* Optimize Boyer-Moore. Use simple mapping Unicode chars to byte. It works well for common text files with chars from one-two languages.

Reviewers

Bruce Payette (BrucePay)

Awaiting requested review from BrucePay

Steve Lee (SteveL-MSFT)

Awaiting requested review from SteveL-MSFT

Aditya Patwardhan (adityapatwardhan)

Awaiting requested review from adityapatwardhan

Dongbo Wang (daxian-dbw)

Awaiting requested review from daxian-dbw

Travis Plunk (TravisEz13)

Awaiting requested review from TravisEz13

2 more reviewers

Andrew (anmenaga)

anmenaga left review comments

Paul Higinbotham (PaulHigin)

PaulHigin approved these changes

Reviewers whose approvals may not affect merge requirements

Uh oh!

There was an error while loading. Please reload this page.

Assignees

Ilya (iSazonov)

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

3 participants

Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.

You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

Conversation

Ilya (iSazonov) commented Oct 22, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

PR Summary

PR Checklist

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Paul Higinbotham (PaulHigin) left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Ilya (iSazonov) commented Oct 24, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Ilya (iSazonov) Oct 25, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Paul Higinbotham (PaulHigin) left a comment

Choose a reason for hiding this comment

Uh oh!

Ilya (iSazonov) commented Oct 25, 2018

Uh oh!

Andrew (anmenaga) commented Oct 25, 2018

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Ilya (iSazonov) commented Oct 22, 2018 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Ilya (iSazonov) commented Oct 24, 2018 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Ilya (iSazonov) Oct 25, 2018 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.