char[] لممارسة سلسلة سداسية

Question

يوجد أدناه وظيفة char* الحالية لسلسلة سداسية عشرية.لقد كتبت ذلك كتمرين في التلاعب بالبت.يستغرق الأمر حوالي 7 مللي ثانية على AMD Athlon MP 2800+ لدمج مصفوفة سعة 10 ملايين بايت.هل هناك أي خدعة أو طريقة أخرى أفتقدها؟

كيف يمكنني أن أجعل هذا أسرع؟

تم تجميعها باستخدام -O3 في g++

static const char _hex2asciiU_value[256][2] =
     { {'0','0'}, {'0','1'}, /* snip..., */ {'F','E'},{'F','F'} };

std::string char_to_hex( const unsigned char* _pArray, unsigned int _len )
{
    std::string str;
    str.resize(_len*2);
    char* pszHex = &str[0];
    const unsigned char* pEnd = _pArray + _len;

    clock_t stick, etick;
    stick = clock();
    for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++, pszHex += 2 ) {
        pszHex[0] = _hex2asciiU_value[*pChar][0];
        pszHex[1] = _hex2asciiU_value[*pChar][1];
    }
    etick = clock();

    std::cout << "ticks to hexify " << etick - stick << std::endl;

    return str;
}

التحديثات

وأضاف رمز التوقيت

بريان ر.بوندي:استبدل std::string بمخزن مؤقت مخصص للكومة وقم بتغيير ofs*16 إلى ofs << 4 - ولكن يبدو أن المخزن المؤقت المخصص للكومة يبطئه؟- النتيجة ~ 11 مللي ثانية

أنتي سيكاري:استبدال الحلقة الداخلية بـ

 int upper = *pChar >> 4;
 int lower = *pChar & 0x0f;
 pszHex[0] = pHex[upper];
 pszHex[1] = pHex[lower];

النتيجة ~ 8 مللي ثانية

روبرت:يستبدل _hex2asciiU_value مع جدول كامل يضم 256 إدخالًا، مما يؤدي إلى التضحية بمساحة الذاكرة ولكن النتيجة تبلغ حوالي 7 مللي ثانية!

هوي هوي:لاحظت أنه كان يعطي نتائج غير صحيحة

Answer 1

على حساب المزيد من الذاكرة، يمكنك إنشاء جدول كامل مكون من 256 إدخالًا للرموز السداسية:

static const char _hex2asciiU_value[256][2] =
    { {'0','0'}, {'0','1'}, /* ..., */ {'F','E'},{'F','F'} };

ثم قم بتوجيه الفهرس إلى الجدول، دون الحاجة إلى أي عبث.

const char *pHexVal = pHex[*pChar];
pszHex[0] = pHexVal[0];
pszHex[1] = pHexVal[1];

Answer 2

تعمل وظيفة التجميع هذه (استنادًا إلى مشاركتي السابقة هنا، ولكن كان علي تعديل المفهوم قليلاً حتى تعمل بالفعل) على معالجة 3.3 مليار حرف إدخال في الثانية (6.6 مليار حرف إخراج) على نواة واحدة من Core 2 Conroe 3Ghz.ربما يكون بنرين أسرع.

%include "x86inc.asm"

SECTION_RODATA
pb_f0: times 16 db 0xf0
pb_0f: times 16 db 0x0f
pb_hex: db 48,49,50,51,52,53,54,55,56,57,65,66,67,68,69,70

SECTION .text

; int convert_string_to_hex( char *input, char *output, int len )

cglobal _convert_string_to_hex,3,3
    movdqa xmm6, [pb_f0 GLOBAL]
    movdqa xmm7, [pb_0f GLOBAL]
.loop:
    movdqa xmm5, [pb_hex GLOBAL]
    movdqa xmm4, [pb_hex GLOBAL]
    movq   xmm0, [r0+r2-8]
    movq   xmm2, [r0+r2-16]
    movq   xmm1, xmm0
    movq   xmm3, xmm2
    pand   xmm0, xmm6 ;high bits
    pand   xmm2, xmm6
    psrlq  xmm0, 4
    psrlq  xmm2, 4
    pand   xmm1, xmm7 ;low bits
    pand   xmm3, xmm7
    punpcklbw xmm0, xmm1
    punpcklbw xmm2, xmm3
    pshufb xmm4, xmm0
    pshufb xmm5, xmm2
    movdqa [r1+r2*2-16], xmm4
    movdqa [r1+r2*2-32], xmm5
    sub r2, 16
    jg .loop
    REP_RET

لاحظ أنه يستخدم بناء جملة التجميع x264، مما يجعله أكثر قابلية للنقل (إلى 32 بت مقابل 64 بت، وما إلى ذلك).لتحويل هذا إلى بناء الجملة الذي تختاره أمر تافه:r0، r1، r2 هي الوسائط الثلاث للوظائف في السجلات.إنه يشبه إلى حد ما الكود الكاذب.أو يمكنك فقط الحصول على common/x86/x86inc.asm من شجرة x264 وتضمين ذلك لتشغيله محليًا.

ملاحظة.Stack Overflow، هل أنا مخطئ في إضاعة الوقت في مثل هذا الشيء التافه؟أم أن هذا رائع؟

Answer 3

تنفيذ أسرع لـ C

يعمل هذا أسرع بثلاث مرات تقريبًا من تطبيق C++.لست متأكدًا من السبب لأنه مشابه جدًا.بالنسبة لتطبيق C++ الأخير الذي قمت بنشره، استغرق الأمر 6.8 ثانية للتشغيل عبر مصفوفة أحرف تبلغ 200,000,000.استغرق التنفيذ 2.2 ثانية فقط.

#include <stdio.h>
#include <stdlib.h>

char* char_to_hex(const unsigned char* p_array, 
                  unsigned int p_array_len,
                  char** hex2ascii)
{
    unsigned char* str = malloc(p_array_len*2+1);
    const unsigned char* p_end = p_array + p_array_len;
    size_t pos=0;
    const unsigned char* p;
    for( p = p_array; p != p_end; p++, pos+=2 ) {
       str[pos] = hex2ascii[*p][0];
       str[pos+1] = hex2ascii[*p][1];
    }
    return (char*)str;
}

int main()
{
  size_t hex2ascii_len = 256;
  char** hex2ascii;
  int i;
  hex2ascii = malloc(hex2ascii_len*sizeof(char*));
  for(i=0; i<hex2ascii_len; i++) {
    hex2ascii[i] = malloc(3*sizeof(char));    
    snprintf(hex2ascii[i], 3,"%02X", i);
  }
  size_t len = 8;
  const unsigned char a[] = "DO NOT WANT";
  printf("%s\n", char_to_hex((const unsigned char*)a, len, (char**)hex2ascii));
}

Answer 4

اعمل على 32 بت في المرة الواحدة (4 أحرف)، ثم تعامل مع الذيل إذا لزم الأمر.عندما قمت بهذا التمرين مع ترميز عنوان url، كان البحث في جدول كامل لكل حرف أسرع قليلاً من البنيات المنطقية، لذلك قد ترغب في اختبار ذلك في السياق أيضًا لأخذ مشكلات التخزين المؤقت في الاعتبار.

Answer 5

يعمل بالنسبة لي مع unsigned char:

unsigned char  c1 =  byteVal >> 4;
unsigned char  c2 =  byteVal & 0x0f;

c1 +=  c1 <= 9 ? '0' : ('a' - 10);
c2 +=  c2 <= 9 ? '0' : ('a' - 10);

std::string sHex("  ");
sHex[0] = c1 ;
sHex[1] = c2 ;


//sHex - contain what we need. For example "0f"

Answer 6

لأحد، بدلا من الضرب 16 افعل أ bitshift << 4

كذلك لا تستخدم std::string, ، بدلاً من ذلك، ما عليك سوى إنشاء مخزن مؤقت على الكومة ثم delete هو - هي.سيكون أكثر كفاءة من تدمير الكائن المطلوب من السلسلة.

Answer 7

لن يحدث فرقا كبيرا..*pChar-(ofs*16) يمكن إجراؤه باستخدام [*pChar & 0x0F]

Answer 8

هذه هي نسختي، والتي، على عكس إصدار OP، لا تفترض ذلك std::basic_string لديه بياناته في منطقة متجاورة:

#include <string>

using std::string;

static char const* digits("0123456789ABCDEF");

string
tohex(string const& data)
{
    string result(data.size() * 2, 0);
    string::iterator ptr(result.begin());
    for (string::const_iterator cur(data.begin()), end(data.end()); cur != end; ++cur) {
        unsigned char c(*cur);
        *ptr++ = digits[c >> 4];
        *ptr++ = digits[c & 15];
    }
    return result;
}

Answer 9

أفترض أن هذا هو Windows + IA32.
حاول استخدام int قصير بدلاً من الحرفين الست عشريين.

short int hex_table[256] = {'0'*256+'0', '1'*256+'0', '2'*256+'0', ..., 'E'*256+'F', 'F'*256+'F'};
unsigned short int* pszHex = &str[0];

stick = clock();

for (const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) 
    *pszHex++ = hex_table[*pChar];

etick = clock();

Answer 10

تغيير

    ofs = *pChar >> 4;
    pszHex[0] = pHex[ofs];
    pszHex[1] = pHex[*pChar-(ofs*16)];

ل

    int upper = *pChar >> 4;
    int lower = *pChar & 0x0f;
    pszHex[0] = pHex[upper];
    pszHex[1] = pHex[lower];

النتائج في ما يقرب من 5٪ تسريع.

كتابة النتيجة بايتين في الوقت المناسب كما اقترح روبرت النتائج في حوالي 18٪ تسريع.يتغير الكود إلى:

_result.resize(_len*2);
short* pszHex = (short*) &_result[0];
const unsigned char* pEnd = _pArray + _len;

const char* pHex = _hex2asciiU_value;
for(const unsigned char* pChar = _pArray;
    pChar != pEnd;
    pChar++, ++pszHex )
{
    *pszHex = bytes_to_chars[*pChar];
}

التهيئة المطلوبة:

short short_table[256];

for (int i = 0; i < 256; ++i)
{
    char* pc = (char*) &short_table[i];
    pc[0] = _hex2asciiU_value[i >> 4];
    pc[1] = _hex2asciiU_value[i & 0x0f];
}

من المحتمل أن يؤدي القيام بذلك بمقدار 2 بايت في المرة الواحدة أو 4 بايت في المرة الواحدة إلى عمليات تسريع أكبر، كما أشار آلان ويند, ، ولكن بعد ذلك يصبح الأمر أكثر صعوبة عندما يتعين عليك التعامل مع الشخصيات الفردية.

إذا كنت تشعر بالمغامرة، فقد تحاول التكيف جهاز داف لفعل هذا.

النتائج على معالج Intel Core Duo 2 و gcc -O3.

قم دائمًا بالقياس أنك تحصل بالفعل على نتائج أسرع - فالتشاؤم الذي يتظاهر بأنه تحسين لا قيمة له.

اختبر دائمًا أن تحصل على النتائج الصحيحة - فالخطأ الذي يتظاهر بأنه تحسين يعد أمرًا خطيرًا تمامًا.

و ضع في اعتبارك دائمًا المقايضة بين السرعة وسهولة القراءة - الحياة قصيرة جدًا بحيث لا يستطيع أي شخص الاحتفاظ بكود غير قابل للقراءة.

(مرجع إلزامي للترميز ل مريض نفسي عنيف يعرف أين تعيش.)

Answer 11

تأكد من تشغيل تحسين برنامج التحويل البرمجي الخاص بك إلى أعلى مستوى عمل.

كما تعلمون، أعلام مثل "-O1" إلى "-03" في دول مجلس التعاون الخليجي.

Answer 12

لقد وجدت أن استخدام فهرس في مصفوفة، بدلاً من المؤشر، يمكن أن يسرع الأمور.كل هذا يتوقف على كيفية اختيار المترجم الخاص بك للتحسين.المفتاح هو أن المعالج لديه تعليمات للقيام بأشياء معقدة مثل [i*2+1] في تعليمات واحدة.

Answer 13

إذا كنت مهووسًا بالسرعة هنا، فيمكنك القيام بما يلي:

كل حرف هو بايت واحد، يمثل قيمتين ست عشرية.وبالتالي، فإن كل حرف هو في الواقع قيمتان من أربع بتات.

لذلك، يمكنك القيام بما يلي:

1. قم بفك ضغط القيم ذات الأربع بتات إلى قيم 8 بتات باستخدام الضرب أو تعليمات مشابهة.
2. استخدم pshufb، تعليمات SSSE3 (مع ذلك، Core2 فقط).فهو يأخذ مصفوفة من 16 قيمة إدخال ذات 8 بتات ويخلطها بناءً على مؤشرات 8 بتات الـ 16 في المتجه الثاني.نظرًا لأن لديك 16 شخصية محتملة فقط، فهذا يناسبك تمامًا؛مصفوفة الإدخال عبارة عن متجه من 0 إلى أحرف F، ومصفوفة الفهرس هي مصفوفة غير مضغوطة من قيم 4 بت.

وهكذا، في أ تعليمات واحدة, ، سوف تكون قد قمت بالأداء 16 عملية بحث للجدول في ساعات أقل مما يتطلبه الأمر عادةً للقيام بساعة واحدة فقط (pshufb هو زمن استجابة ساعة واحدة على Penryn).

لذلك، في الخطوات الحسابية:

1. A B C D E F G H I J K L M N O P (متجه 64 بت لقيم الإدخال، "Vector A") -> 0A 0B 0C 0D 0E 0F 0G 0H 0I 0J 0K 0L 0M 0N 0O 0P (متجه 128 بت للمؤشرات، "Vector B").ربما تكون أسهل طريقة هي مضاعفتان 64 بت.
2. pshub [0123456789ABCDEF]، فيكتور ب

Answer 14

لست متأكدًا من أن القيام بذلك بمزيد من البايتات في المرة الواحدة سيكون أفضل ...من المحتمل أن تحصل على الكثير من الأخطاء في ذاكرة التخزين المؤقت وتبطئها بشكل ملحوظ.

ما قد تحاول فعله هو فتح الحلقة، واتخاذ خطوات أكبر وإجراء المزيد من الأحرف في كل مرة خلال الحلقة، لإزالة بعض الحمل الزائد للحلقة.

Answer 15

الحصول باستمرار على ~ 4 مللي ثانية على جهاز Athlon 64 4200+ (حوالي 7 مللي ثانية مع الكود الأصلي)

for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) {
    const char* pchars = _hex2asciiU_value[*pChar];
    *pszHex++ = *pchars++;
    *pszHex++ = *pchars;
}

Answer 16

الوظيفة كما تظهر عندما أكتب هذا تنتج مخرجات غير صحيحة حتى عندما يتم تحديد _hex2asciiU_value بالكامل.يعمل الكود التالي، وعلى جهاز Macbook Pro الذي يعمل بتردد 2.33 جيجا هرتز، يعمل في حوالي 1.9 ثانية لـ 200,000,000 مليون حرف.

#include <iostream>

using namespace std;

static const size_t _h2alen = 256;
static char _hex2asciiU_value[_h2alen][3];

string char_to_hex( const unsigned char* _pArray, unsigned int _len )
{
    string str;
    str.resize(_len*2);
    char* pszHex = &str[0];
    const unsigned char* pEnd = _pArray + _len;
    const char* pHex = _hex2asciiU_value[0];
    for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++, pszHex += 2 ) {
       pszHex[0] = _hex2asciiU_value[*pChar][0];
       pszHex[1] = _hex2asciiU_value[*pChar][1];
    }
    return str;
}


int main() {
  for(int i=0; i<_h2alen; i++) {
    snprintf(_hex2asciiU_value[i], 3,"%02X", i);
  }
  size_t len = 200000000;
  char* a = new char[len];
  string t1;
  string t2;
  clock_t start;
  srand(time(NULL));
  for(int i=0; i<len; i++) a[i] = rand()&0xFF;
  start = clock();
  t1=char_to_hex((const unsigned char*)a, len);
  cout << "char_to_hex conversion took ---> " << (clock() - start)/(double)CLOCKS_PER_SEC << " seconds\n";
}