멀티코어 텍스트 파일 구문 분석

Question

저는 쿼드 코어 시스템을 가지고 있으며 4개의 코어를 모두 활용하는 텍스트 파일을 구문 분석하는 코드를 작성하고 싶습니다.텍스트 파일에는 기본적으로 한 줄에 하나의 레코드가 포함됩니다.

멀티스레딩은 제 장점이 아니기 때문에 최적의 방식으로 파일을 구문 분석하는 데 사용할 수 있는 몇 가지 패턴을 누군가 제게 줄 수 있는지 궁금합니다.

내 첫 번째 생각은 모든 라인을 일종의 대기열로 읽은 다음 스레드를 스핀업하여 대기열에서 라인을 가져와 처리하는 것입니다. 그러나 이는 대기열이 메모리에 존재해야 하며 상당히 큰 파일이므로 난 그런 생각은 별로 좋아하지 않아.

내 다음 생각은 라인을 읽고 구문 분석할 스레드를 할당하는 일종의 컨트롤러를 갖는 것입니다. 그러나 스레드가 가능한 것보다 더 빠르게 라인을 처리하는 경우 컨트롤러가 결국 병목 현상을 일으킬지는 확실하지 않습니다. 읽고 할당하세요.

나는 아마도 이 두 가지보다 더 간단한 해결책이 있을 것이라는 것을 알고 있지만 지금은 그것을 볼 수 없습니다.

Answer 1

나는 당신의 독창적인 아이디어를 따르겠습니다.대기열이 너무 커질 수 있다는 우려가 있는 경우 대기열에 대한 버퍼 영역을 구현합니다(예:100줄 이상이면 파일 읽기가 중지되고, 20줄 미만이면 다시 읽기 시작됩니다.최적의 장벽을 찾으려면 몇 가지 테스트를 수행해야 합니다.항목을 꺼내기 위해 큐를 잠가야 하므로 스레드 중 하나가 잠재적으로 "리더 스레드"가 될 수 있도록 만드십시오. 어쨌든 "낮은 버퍼 영역"에 도달했는지 확인하고 다시 읽기를 시작할 수도 있습니다.이 작업을 수행하는 동안 다른 스레드는 대기열의 나머지 부분을 읽을 수 있습니다.

또는 원하는 경우 하나의 리더 스레드가 다른 세 개의 행에 줄을 할당하도록 합니다. 프로세서 스레드를 (자체 대기열을 통해) 구현하고 일을 훔치는 전략.저는 이런 일을 해본 적이 없어서 얼마나 힘든 일인지 모릅니다.

Answer 2

Mark의 답변은 더 간단하고 우아한 솔루션입니다.필요하지 않은 경우 스레드 간 통신을 사용하여 복잡한 프로그램을 구축하는 이유는 무엇입니까?4개의 스레드를 생성합니다.각 스레드는 파일 크기/4를 계산하여 시작 지점(및 중지 지점)을 결정합니다.그러면 각 스레드는 완전히 독립적으로 작동할 수 있습니다.

그만큼 오직 읽기를 처리하기 위해 특수 스레드를 추가하는 이유는 일부 줄을 처리하는 데 매우 오랜 시간이 걸릴 것으로 예상되는 경우입니다. 그리고 이러한 줄은 파일의 단일 부분에 클러스터되어 있다고 예상합니다.필요하지 않을 때 스레드 간 통신을 추가하는 것은 아주 나쁜 생각.예상치 못한 병목 현상 및/또는 동기화 버그가 발생할 가능성이 크게 높아집니다.

Answer 3

이렇게 하면 단일 스레드가 읽기를 수행하는 데 따른 병목 현상이 제거됩니다.

open file
for each thread n=0,1,2,3:
    seek to file offset 1/n*filesize
    scan to next complete line
    process all lines in your part of the file

Answer 4

내 경험은 C#이 아닌 Java에 관한 것이므로 이러한 솔루션이 적용되지 않으면 사과드립니다.

내가 생각해 낼 수 있는 즉각적인 해결책은 3개의 스레드를 실행하는 실행기를 갖는 것입니다(다음을 사용). Executors.newFixedThreadPool, 말하다).입력 파일에서 읽은 각 라인/레코드에 대해 실행기에서 작업을 시작합니다(다음을 사용). ExecutorService.submit).실행자는 요청을 대기열에 추가하고 3개의 스레드 사이에 할당합니다.

아마도 더 나은 솔루션이 있을 수 있지만 그것이 효과가 있기를 바랍니다.:-)

예상 시간:Wolfbyte의 두 번째 솔루션과 매우 흡사합니다.:-)

도착 예정 시간2: System.Threading.ThreadPool .NET에서도 매우 유사한 아이디어처럼 들립니다.나는 그것을 사용해 본 적이 없지만 가치가 있을 것입니다!

Answer 5

병목 현상은 일반적으로 파일을 처리할 때 읽기가 아니라 처리 중에 발생하므로 생산자-소비자 무늬.잠금을 피하기 위해 잠금 해제 목록을 살펴보겠습니다.C#을 사용하고 있으므로 Julian Bucknall의 내용을 살펴볼 수 있습니다. 잠금 해제 목록 암호.

Answer 6

@lomaxx

@데릭 & 마크:2가지 답변을 받아들일 수 있는 방법이 있었으면 좋겠습니다.파일을 n개의 섹션으로 분할하면 스레드가 "느린" 트랜잭션 배치를 발견할 가능성이 있기 때문에 Wolfbyte의 솔루션을 사용해야 합니다. 그러나 각 프로세스가 있는 파일을 처리하는 경우 동일한 양의 처리가 필요하다는 것이 보장되었으므로 파일을 청크로 분할하고 각 청크를 스레드에 할당하고 완료하는 솔루션이 정말 마음에 듭니다.

걱정 마.클러스터된 "느린" 트랜잭션이 문제인 경우 큐잉 솔루션을 사용하는 것이 좋습니다.평균 트랜잭션의 속도에 따라 각 작업자에게 한 번에 여러 라인을 할당하는 방법을 살펴볼 수도 있습니다.이렇게 하면 동기화 오버헤드가 줄어듭니다.마찬가지로 버퍼 크기를 최적화해야 할 수도 있습니다.물론 이 두 가지 모두 프로파일링 후에만 수행해야 하는 최적화입니다.(병목 현상이 발생하지 않는다면 동기화에 대해 걱정할 필요가 없습니다.)

Answer 7

구문 분석 중인 텍스트가 반복되는 문자열과 토큰으로 구성된 경우 파일을 청크로 나누고 각 청크에 대해 하나의 스레드를 키워드, "구두점", ID 문자열 및 값으로 구성된 토큰으로 미리 구문 분석하도록 할 수 있습니다.문자열 비교 및 ​​조회는 상당히 비용이 많이 들 수 있으며 이를 여러 작업자 스레드에 전달하면 문자열 조회 및 비교를 수행할 필요가 없는 경우 코드의 순전히 논리적/의미적 부분의 속도를 높일 수 있습니다.

사전 구문 분석된 데이터 청크(이미 모든 문자열 비교를 수행하고 "토큰화"한)는 토큰화된 데이터의 의미와 순서를 실제로 확인하는 코드 부분으로 전달될 수 있습니다.

또한, 많은 양의 메모리를 차지하는 파일 크기가 걱정된다고 언급하셨습니다.메모리 예산을 줄이기 위해 할 수 있는 몇 가지 방법이 있습니다.

파일을 청크로 분할하고 구문 분석합니다.한 번에 작업하는 만큼의 청크와 "미리 읽기"를 위한 몇 개의 청크만 읽어서 청크 처리를 마친 후 다음 청크로 이동하기 전에 디스크에서 정지하지 않도록 하세요.

또는 대용량 파일을 메모리 매핑하고 "요구"를 로드할 수 있습니다.파일 처리에 CPU보다 더 많은 스레드가 있는 경우(일반적으로 스레드 = 1.5-2X CPU가 요구 페이징 앱에 적합함) 메모리 매핑된 파일에 대한 IO에서 지연되는 스레드는 해당 작업이 완료될 때까지 OS에서 자동으로 중지됩니다. 메모리가 준비되었으며 다른 스레드는 계속 처리됩니다.